首页 > 代码库 > 【poj 1961】Period（字符串--KMP循环节）

【poj 1961】Period（字符串--KMP循环节）

2024-08-21 12:54:07   218人阅读

题意：给你一个字符串，求这个字符串到第 i 个字符为止的重复子串的个数。

解法：判断重复子串的语句很重要！！if (p && i%(i-p)==0) printf("%d %d\n",i,i/(i-p));

     我之前一直不是很理解，而实际上多枚举几种情况就好了。若是重复的，那么next[i]肯定是最大值，值余下一个循环节不同；而若不是，next[i]表示的前缀和后缀串的和重叠部分不一样以外的部分就肯定空出来，不能整除的。（P.S.我在说些什么......ｍ（．＿．）ｍ）

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6  7 const int N=1000010; 8 int next[N]; 9 int n;10 char s[N];11 12 void kmp()13 {14     memset(next,0,sizeof(next));15     int p=0;16     next[1]=0;17     for (int i=2;i<=n;i++)18     {19       while (s[i]!=s[p+1] && p) p=next[p];20       if (s[i]==s[p+1]) p++;21       next[i]=p;22       if (p && i%(i-p)==0)//p23         printf("%d %d\n",i,i/(i-p));24     }25 }26 int main()27 {28     int T=0;29     while (1)30     {31       scanf("%d",&n);32       if (!n) break;33       scanf("%s",s+1);34       if (T) printf("\n");35       printf("Test case #%d\n",++T);36       kmp();37     }38     return 0;39 }

 

【poj 1961】Period（字符串--KMP循环节）


联系
我们