KMP专题

1、【HDU 3336】Count the string(KMP+dp)

题意：求给定字符串含前缀的数量，如输入字符串abab，前缀是a、ab、aba、abab，在原字符串中出现的次数分别是2、2、1、1，所以答案是2+2+1+1=6.

解题思路：s[]=abcdabcdabcdea ==> f[] = 00001234567801，f[i]=k的含义是s[i-k]=s[i]，dp[i]=dp[f[i]]+1，dp[i]表示以s[i]结尾的前缀的数量

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <string>

 using namespace std;

 #define ll __int64

 const int N=*1e5+;

 const ll mod=;

 char p[N];

 ll f[N], ans[N];

 int lenp;

 void getf()

 {

     memset(f, , sizeof(f));

     int i,j;

     j=f[]=;

     i=;

     while(i<lenp)

     {

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

         if(p[i+] == p[j+]) j++;

         f[++i] = j;

     }

 }

 int main(){

     int t;

     scanf("%d", &t);

     while(t--){

         memset(ans, , sizeof(ans));

         memset(p, '\0', sizeof(p));

         scanf("%d%s", &lenp, p+);

         getf();

         ll sum=;

         for(int i=; i<=lenp; i++) ans[i] = (ans[f[i]]+)%mod;

         for(int i=; i<=lenp; i++) sum = (sum+ans[i])%mod;

         printf("%I64d\n", sum);

 //        for(int i=1; i<=lenp; i++) cout<<f[i];

 //\        cout<<endl;

     }

     return ;

 }

2、【POJ 2406】Power Strings

题意：如果字符串a=”abc”，字符串b=”def”，那么a*b=”abcdef”，输入字符串s，那么s=x^n中n的最大值。

解题思路：求n的最大值也就是求s的最小循环节【s[]=abcdabcdabcdea ==> f[] = 00001234567801，最小循环节只能是len-f[len]】然后判断len是否能整除最小循环节，如果不能整除，那么n最大值只能是1

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <string>

 using namespace std;

 const int N=;

 char s[N];

 int f[N], lens;

 void getf(){

     memset(f, , sizeof(f));

     int i, j;

     j=f[]=-;

     i=;

     while(i<lens){

         while(j!=- && s[i+]!=s[j+]) j = f[j];

         f[++i] = ++j;

     }

 }

 int main(){

     while(~scanf("%s", s)){

         lens = strlen(s);

         if(lens== && s[]=='.') break;

         getf();

         f[lens-]++;

         int ans = lens-f[lens-];

         if(lens%ans==) ans = lens/ans;

         else ans=;

         printf("%d\n", ans);

     }

     return ;

 }

3、【HDU 1867】A + B for you again

题意：输入两个字符串(len<=1e5)A、B，s1=A+B【去掉了A的后缀跟B的前缀相等部分】，s2=B+A【去掉了B的后缀跟A的前缀相等部分】，输出s1跟s2其中一个，先考虑长度小的，长度差相等的时候考虑字典序小的。

解题思路：关键是求出A的后缀与B的前缀以及B的后缀跟A的前缀重叠部分的长度。A的后缀跟B的前缀重叠部分的求法：求出B的fp[]，拿B去匹配A，如果能一直匹配到最后一位，那么重叠部分就是B已经匹配了的长度。

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <string>

 using namespace std;

 const int N=1e5+;

 char s[N], p[N];

 int fs[N], fp[N], lens, lenp;

 void kmp_getfs(){

     memset(fs, , sizeof(fs));

     int i, j;

     i=, j=fs[]=;

     while(i<=lens){

         while(j!= && s[i]!=s[j+]) j = fs[j];

         if(s[i] == s[j+]) j++;

         fs[i++]=j;

     }

 }

 void kmp_getfp(){

     memset(fp, , sizeof(fp));

     int i, j;

     i=, j=fp[]=;

     while(i<=lenp){

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

         if(p[i] == p[j+]) j++;

         fp[i++] = j;

     }

 }

 int main(){

     while(~scanf("%s%s", s+, p+)){

         lens = strlen(s+);

         lenp = strlen(p+);

         kmp_getfs();

         kmp_getfp();

         int is=, jp=, flags=;

         for(is=; is<=lens; is++){

             while(jp!= && s[is]!=p[jp+]) jp=fp[jp];

             if(s[is]==p[jp+]){

                 jp++;

                 if(is==lens) flags=;

             }

         }

         int ip=, js=, flagp=;

         for(ip=; ip<=lenp; ip++){

             while(js!= && p[ip]!=s[js+]) js = fs[js];

             if(p[ip] == s[js+]){

                 js++;

                 if(ip==lenp) flagp=;

             }

         }

         int sums=lens+lenp-jp;

         int sump=lens+lenp-js;

         if(sums==sump){

             string sp, ps;

             sp.clear(), ps.clear();

             for(int i=; i<=lens; i++) sp+=s[i];

             for(int i=jp+; i<=lenp; i++) sp+=p[i];

             for(int i=; i<=lenp; i++) ps+=p[i];

             for(int i=js+; i<=lens; i++) ps+=s[i];

             if(sp>ps) cout<<ps<<endl;

             else cout<<sp<<endl;

         }

         else if(sums>sump){

             printf("%s", p+);

             for(int i=js+; i<=lens; i++) cout<<s[i];

             cout<<endl;

         }

         else if(sums<sump){

             printf("%s", s+);

             for(int i=jp+; i<=lenp; i++) cout<<p[i];

             cout<<endl;

         }

     }

     return ;

 }

巴特西

KMP专题

最新文章

热门文章