FZU - 1901 Period II （kmp）

传送门：FZU - 1901

题意：给你个字符串，让你求有多少个p可以使S[i]==S[i+P] (0<=i<len-p-1)。

题解：这个题是真的坑，一开始怎么都觉得自己不可能错，然后看了别人的博客打脸了，发现自己掉坑了了...一开始想的是找出最小循环节，只要每次输出多加一个循环节，最后输出len就好了。后来发现最小循环节的倍数并不能表示所有循环节。看到的一组例子ababaaaabab，应该输出7，9，11；但是最小循环节的输出是7，11。

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<string.h>

 4 #include<queue>

 5 using namespace std;

 6

 7 char a[1000100];

 8 int nt[1000100];

 9

10 void kmp_nt(int m)

11 {

12     int i,j;

13     i = 0;

14     nt[0] = j =-1;

15     while(i < m){

16         while(j!=-1&&a[i]!=a[j])

17             j = nt[j];

18         if(a[i]==a[j]||j==-1){

19             i++;

20             j++;

21             nt[i]=j;

22         }

23     }

24 }

25

26 int main()

27 {

28     int t;

29     cin>>t;

30     for(int i=1;i<=t;i++){

31         cin>>a;

32         cout<<"Case #"<<i<<": ";

33         int len=strlen(a);

34         kmp_nt(len);

35         queue<int>q;

36         int ans=nt[len];

37         while(ans>0){

38             q.push(ans);

39             ans=nt[ans];

40         }

41         cout<<q.size()+1<<endl;

42         while(!q.empty()){

43             cout<<len-q.front()<<' ';

44             q.pop();

45         }

46         cout<<len<<endl;

47     }

48     return 0;

49 }

巴特西

FZU - 1901 Period II （kmp）

最新文章

热门文章