LA - 3026 - Period(KMP)

2023-11-03 13:18
文章标签 kmp la period 3026

本文主要是介绍LA - 3026 - Period(KMP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:求一个字符串每个前缀的最短循环节,输出前缀i的长度和循环节的长度。

题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1027

——>>第一道KMP题目……照汝佳的书敲下……

#include <cstdio>using namespace std;const int maxn = 1000000 + 10;
char P[maxn];
int f[maxn];int main()
{int n, kase = 0;while(scanf("%d", &n) == 1 && n){scanf("%s", P);f[0] = 0;f[1] = 0;for(int i = 1; i < n; i++){int j = f[i];while(j && P[i] != P[j]) j = f[j];f[i+1] = (P[i] == P[j] ? j+1 : 0);}printf("Test case #%d\n", ++kase);for(int i = 2; i <= n; i++)if(f[i] > 0 && i % (i-f[i]) == 0) printf("%d %d\n", i, i/(i-f[i]));printf("\n");}return 0;
}


这篇关于LA - 3026 - Period(KMP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/338420

相关文章

codeforces535D:Tavas and Malekas(KMP)

(i-1 , i)有重合的时候 ,从第i位开始的子串必须是模式串的前缀。 而同时,从第i位开始的子串本来就已经是模式串的后缀了。 typedef long long LL ;const int maxn = 1000008 ;int next[maxn] ;void getnext(char s[]){int len = strlen(s) ;next[0] = -1 ;i

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

jmeter线程组的ramp-up period 设置

Ramp-Up period(in seconds):用于告知JMeter 要在多长时间内建立全部的线程。默认值是0。如果未指定ramp-up period ,也就是说ramp-up period 为零, JMeter 将立即建立所有线程,假设ramp-up period 设置成1秒, 全部线程数设置成2个, JMeter 将每隔0.5秒建立一个线程(即ramp-up period时间内执行完所有

KMP 详解

KMP数组存的是什么 对于一个字符串 b,下标从1开始。 则kmp[i]表示 以i结尾的连续子串 = s的前缀的最大值(等价于前缀最大结尾处) 如何求KMP 假设 i 以前的KMP都被求出来了。 j 表示上一个字符可以成功匹配的长度(等价于下标) 如果b[j+1] != b[i]下一个位置匹配不上(即不能成为前缀) 则,让j = kmp[j] 即成为以j结尾的 连续子串 的 最长前缀

La-Z-Boy 标签制作注意事项

在制作标签之前,供应商需要通过EDI向La-Z-Boy发送提前发货通知(ASN)。ASN中的每个明细行将会至少对应一个运输编号(shipment ID),这个信息将会被体现在运输标签上,和标签上的条形码一起,用于La-Z-Boy收货。 供应商必须确保其装箱单以及发票中的信息能够对应上该批次货物的运输标签以及相关运输编号。供应商可以在La-Z-Boy提供的标签文档中,找到La-Z-Boy EDI部

KMP算法详解 --- 彻头彻尾理解KMP算法

前言     之前对kmp算法虽然了解它的原理,即求出P0···Pi的最大相同前后缀长度k。   但是问题在于如何求出这个最大前后缀长度呢?   我觉得网上很多帖子都说的不是很清楚,总感觉没有把那层纸戳破,   后来翻看算法导论32章 字符串匹配,虽然讲到了对前后缀计算的正确性,但是大量的推理证明不大好理解,没有与程序结合起来讲。   今天我在这里讲一讲我的一些理解,希望大家多多指教

扩展KMP --- HDU 3613 Best Reward

Best Reward Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3613   Mean:  给你一个字符串,每个字符都有一个权值(可能为负),你需要将这个字符串分成两个子串,使得这两个子串的价值之和最大。一个子串价值的计算方法:如果这个子串是回文串,那么价值就是这个子串所有字符权值之和;否则价值为0。

数据结构串的实现以及KMP改进算法

</pre><pre name="code" class="cpp">#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 40 /* 存储空间初始分配量 */typedef int Status; /* Status是

Android 解决 No static method in class La/a/a/a; or its super classes

错误堆栈: Process: com.chaozh.iReader, PID: 24217java.lang.NoSuchMethodError: No static method getDrawable(Landroid/content/Context;I)Landroid/graphics/drawable/Drawable; in class La/a/a/a; or its super

字符串匹配算法之KMP算法和BM算法

[尊重原创]-原文链接在这里->http://blogread.cn/it/article/3975?f=wb 本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。下文分别