FZU 1901 Period II (KMP)

2024-04-09 13:18

文章标签 ii kmp 1901 fzu period

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

Problem 1901 Period II

Accept: 518 Submit: 1270
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

For each prefix with length P of a given string S,if

S[i]=S[i+P] for i in [0..SIZE(S)-p-1],

then the prefix is a “period” of S. We want to all the periodic prefixs.

Input

Input contains multiple cases.

The first line contains an integer T representing the number of cases. Then following T cases.

Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.

Output

For each test case, first output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.

Sample Input

4oooacmacmacmacmacmafzufzufzufstostootssto 

Sample Output

Case #1: 31 2 3Case #2: 63 6 9 12 15 16Case #3: 43 6 9 10Case #4: 29 12 

Source

FOJ有奖月赛-2010年05月

思路：对于任意i属于[0,size(s)-p-1]要满足s[i]=s[i+p]，所以必有s[size(s)-p-1]=s[size(s)-1]，即s[size(s)-p-1]就是next数组中存的匹配的那个位置。所以可以循环直到不再匹配为止。用s[size(s)-1]减去每一次循环中得到的位置就是所求的p长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_N 1000005
using namespace std;
char p[MAX_N];
int ne[MAX_N],ans[MAX_N];;
void makeNext(const char p[],int ne[])
{int len=strlen(p);ne[0]=0;for(int i=1,k=0;i<len;i++){while(k>0&&p[i]!=p[k]) k=ne[k-1];if(p[i]==p[k]) k++;ne[i]=k;}
}
int main()
{int t;scanf("%d",&t);for(int k=1;k<=t;k++){scanf("%s",p);memset(ne,0,sizeof(ne));makeNext(p,ne);int len=strlen(p),f=ne[len-1],cnt=0;while(f>0){ans[++cnt]=len-f;f=ne[f-1];}ans[++cnt]=len;printf("Case #%d: %d\n",k,cnt);for(int i=1;i<=cnt;i++){if(i==cnt)printf("%d\n",ans[i]);else printf("%d ",ans[i]);}}return 0;
}

这篇关于FZU 1901 Period II (KMP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！