UVALive - 3026 - Period (KMP)

UVALive - 3026

Period

Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu

Submit Status

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 ≤ i ≤ N)
we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Input

The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 ≤ N ≤ 1 000 000) ? the size of the string S. The second line contains the string S. The input
file ends with a line, having the number zero on it.

Output

For each test case, output ?Test case #? and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K
separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Source

Regionals 2004 >> Europe
- Southeastern

AC代码(还有点纠结):

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1000005;
char str[maxn];
int next[maxn];

int main() {
	int n, cas = 1;
	while(scanf("%d", &n) == 1 && n) {
		scanf("%s", str);
		next[0] = 0, next[1] = 0;
		for(int i = 1; i < n; i++) {
			int j = next[i];
			while(j && str[i] != str[j]) j = next[j];
			next[i+1] = (str[i] == str[j] ? j+1 : 0);
		}

		printf("Test case #%d\n", cas++);
		for(int i = 2; i <= n; i++)
			if(next[i] > 0 && i % ( i - next[i] ) == 0)
				printf("%d %d\n", i, i / (i - next[i]));
		printf("\n");
	}
	return 0;
} 
时间: 02-19

UVALive - 3026 - Period (KMP)的相关文章

UVALive 3026 Period (KMP算法简介)

kmp的代码很短,但是不太容易理解,还是先说明一下这个算法过程吧. 朴素的字符串匹配大家都懂,但是效率不高,原因在哪里? 匹配过程没有充分利用已经匹配好的模版的信息,比如说, i是文本串当前字符的下标,j是要匹配的模版串当前正在匹配的字符的下标.(下标都从零开始) 当匹配到i = 4, j = 4的时候失配了,朴素的匹配做法是往右边移一位然后从j开始扫,这样做效率很低. 不难发现前面已经匹配好的串ab是相同的最大前缀后缀.把串移动到后缀的第一个位置正好是 朴素的匹配过程中第一次匹配能把这个前缀匹

poj1961 &amp; hdu 1358 Period(KMP)

poj 题目链接:http://poj.org/problem?id=1961 hdu题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358 Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether

LA 3026 Period (strings)

Period Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether

HDU - 1358 - Period (KMP)

Period Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4325    Accepted Submission(s): 2087 Problem Description For each prefix of a given string S with N characters (each character has an ASCI

Period(kmp)

Period Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4437    Accepted Submission(s): 2145 Problem Description For each prefix of a given string S with N characters (each character has an ASCII

HDU 1358 Period(kmp)

next数组的应用 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #define L(x) (x<<1) #define R(x) (x<<1|1) #def

【暑假】[实用数据结构]UVAlive 3026 Period

UVAlive 3026 Period 题目: Period Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive),

HDU3336-Count the string(KMP)

Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4449    Accepted Submission(s): 2094 Problem Description It is well known that AekdyCoin is good at string problems as well as n

CQU 单词替换(KMP)

单词替换(KMP) Time Limit: 500 MS Memory Limit: 64000 K Description 给出一个仅包含小写字母的字符串s,和单词A,B.把s中所有的出现过的A替换为B. Input 第一行一个数T(1<=T<=10),表示数据组数 每组数据三行,第一行为s,第二行为A,第三行为B.所有字符串仅包含小写字母 且长度小于5,000,000. Output 每组数据输出一行,替换后的字符串. Sample Input 3 aaa a b aaa aa b aba