FZU1901 Period II —— KMP next数组

时间：2023-03-09 18:10:21
FZU1901 Period II —— KMP next数组

题目链接：https://vjudge.net/problem/FZU-1901

FZU1901 Period II —— KMP next数组 Problem 1901 Period II

Accept: 575    Submit: 1495
Time Limit: 1000 mSec    Memory Limit : 32768 KB

FZU1901 Period II —— KMP next数组 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.

FZU1901 Period II —— KMP next数组 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.

FZU1901 Period II —— KMP next数组 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.

FZU1901 Period II —— KMP next数组 Sample Input

4
ooo
acmacmacmacmacma
fzufzufzuf
stostootssto

FZU1901 Period II —— KMP next数组 Sample Output

Case #1: 3
1 2 3
Case #2: 6
3 6 9 12 15 16
Case #3: 4
3 6 9 10
Case #4: 2
9 12

FZU1901 Period II —— KMP next数组 Source

FOJ有奖月赛-2010年05月

题解：

求出该字符串的所有循环节。

求出字符串的next数组。可知len-next[len]就是字符串的最小循环节，然后next数组回退，len-next[next[len]]就是第二小循环节……

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const double eps = 1e-;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 char x[MAXN];

 int Next[MAXN];

 void get_next(char x[], int m)

 {

     int i, j;

     j = Next[] = -;

     i = ;

     while(i<m)

     {

         while(j!=- && x[i]!=x[j]) j = Next[j];

         Next[++i] = ++j;

     }

 }

 int ans[MAXN];

 int main()

 {

     int T, kase = ;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%s", x);

         int len = strlen(x);

         get_next(x, len);

         int cnt = ;

         for(int k = Next[len]; k!=-; k = Next[k])

             ans[++cnt] = len-k;

         printf("Case #%d: %d\n", ++kase, cnt);

         for(int i = ; i<=cnt; i++)

         {

             printf("%d", ans[i]);

             if(i!=cnt) printf(" ");

         }

         printf("\n");

     }

 }

相关文章