UVAlive 3026 KMP 最小循环节

KMP算法：

一：next数组：next[i]就是前面长度为i的字符串前缀和后缀相等的最大长度，也即索引为i的字符失配时的前缀函数。

二：KMP模板

 /*

 pku3461(Oulipo), hdu1711(Number Sequence)

 这个模板 字符串是从0开始的

 Next数组是从1开始的

 */

 #include <iostream>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 int _next[maxn];

 char S[maxn], T[maxn];

 int slen, tlen;

 void getNext()

 {

     int j, k;

     j = ; k = -; _next[] = -;

     while(j < tlen)

         if(k == - || T[j] == T[k])

             _next[++j] = ++k;

         else

             k = _next[k];

 }

 /*

 }

 返回模式串T在主串S中首次出现的位置

 返回的位置是从0开始的。

 */

 int KMP_Index()

 {

     int i = , j = ;

     getNext();

     while(i < slen && j < tlen)

     {

         if(j == - || S[i] == T[j])

         {

             i++; j++;

         }

         else

             j = _next[j];

     }

     if(j == tlen)

         return i - tlen;

     else

         return -;

 }

 /*

 返回模式串在主串S中出现的次数

 */

 int KMP_Count()

 {

     int ans = ;

     int i, j = ;

     if(slen ==  && tlen == )

     {

         if(S[] == T[])

             return ;

         else

             return ;

     }

     getNext();

     for(i = ; i < slen; i++)

     {

         while(j >  && S[i] != T[j])

             j = _next[j];

         if(S[i] == T[j])

             j++;

         if(j == tlen)

         {

             ans++;

             j = _next[j];

         }

     }

     return ans;

 }

 int main()

 {

     int TT;

     int i, cc;

     cin>>TT;

     while(TT--)

     {

         cin>>S>>T;

         slen = strlen(S);

         tlen = strlen(T);

         cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()<<endl;

         cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl;

     }

     return ;

 }

三：KMP最小循环节、循环周期：

定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

学习博客 https://www.cnblogs.com/chenxiwenruo/p/3546457.html

　　　　https://www.cnblogs.com/c-cloud/p/3224788.html

循环节例题

题目链接 https://vjudge.net/problem/UVALive-3026

解析每个前缀的最小循环节 KMP跑一边判断能不能整除就可以了

AC代码

 #include <bits/stdc++.h>

 #define pb push_back

 #define mp make_pair

 #define F first

 #define S second

 #define all(a) (a).begin(), (a).end()

 #define fillchar(a, x) memset(a, x, sizeof(a))

 #define huan printf("\n");

 using namespace std;

 typedef long long ll;

 const int maxn=1e6+,inf=0x3f3f3f3f;

 const ll mod=1e9+;

 char p[maxn];

 int f[maxn];

 int main()

 {

     int n,kase=;

     while(scanf("%d",&n)==&&n)

     {

         scanf("%s",p);

         f[]=,f[]=;

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

         {

             int j=f[i];

             while(j&&p[i]!=p[j]) j=f[j];

             f[i+]=(p[i]==p[j]?j+:);

         }

         printf("Test case #%d\n", ++kase);

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

         {

             if(f[i]>&&i%(i-f[i])==)

                 printf("%d %d\n",i,i/(i-f[i]));

         }

         huan;

     }

 }

巴特西

UVAlive 3026 KMP 最小循环节

最新文章

热门文章