区块链技术博客
www.b2bchain.cn

kmp算法题全套svp版的讲解

这篇文章主要介绍了kmp算法题全套svp版的讲解,通过具体代码讲解7393并且分析了kmp算法题全套svp版的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了kmp算法题全套svp版的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7393.html。具体如下:

题目链接
1.A – Number Sequence
2.B – Oulipo
3.C – 剪花布条
4.D – Cyclic Nacklace
5.E – PeriodE – Period
6.F – Power Strings
7.G – Seek the Name, Seek the Fame
8.H – Blue Jeans
9.I – Simpsons’ Hidden Talents

10.J – Count the string

11.K – Clairewd’s message

12.L – Substrings

做个总结
代码块上

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; int b[20005]; int a[2000005],f[2000005]; int m,n; void fc() {       f[0]=f[1]=-1;   for(int i=1;i<m;i++)     {  int j=f[i-1];          while((j>=0)&&(b[j+1]!=b[i]))       {          j=f[j];       }         if(b[j+1]==b[i])         {             f[i]=j+1;         }         else         {             f[i]=-1;         }     }  } int kmp() {     int i=0;     int j=0;     while(i<n)     {         if(a[i]==b[j])         {             i++;             j++;             if(j==m)             {                 return i-m+1;             }         }         else         {                 if(j==0)                 {                     i++;                 }                 else                 {                     j=f[j-1]+1;                 }          }     }     return -1; } int main() {     int t;    scanf("%d",&t);     while(t--)    {     scanf("%d",&n);     scanf("%d",&m);    for(int i=0;i<n;i++)    {     scanf("%d",&a[i]);     }    for(int j=0;j<m;j++)    {      scanf("%d",&b[j]);    }   // memset(f,0,sizeof(f));         fc();        printf("%dn",kmp());    }     return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[20005],a[2000005]; int f[2000005];  void fc() {     int k,m,p;    k=strlen(b);     f[0]=f[1]=-1;   for(int i=1;i<k;i++)     {         int j=f[i-1];          while((j>=0)&&(b[j+1]!=b[i]))       {          j=f[j];       }         if(b[j+1]==b[i])         {             f[i]=j+1;         }         else         {             f[i]=-1;         }     }  } int kmp() {     int sum=0;     int i=0;     int j=0;     int k=strlen(a);     int m=strlen(b);     while(i<k)     {         if(a[i]==b[j])         {             i++;             j++;             if(j==m)             {                 sum++;             }         }         else         {                 if(j==0)                 {                     i++;                 }                 else                 {                     j=f[j-1]+1;                 }          }     }     return sum; } int main() {     int t;    scanf("%d",&t);     while(t--)    {      scanf(" %s",b);     scanf(" %s",a);     //memset(f,0,sizeof(f));         fc();        printf("%dn",kmp());    }     return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[20005],a[2000005]; int f[2000005];  void fc() {     int k;    k=strlen(b);     f[0]=f[1]=-1;   for(int i=1;i<k;i++)     {         int j=f[i-1];          while((j>=0)&&(b[j+1]!=b[i]))       {          j=f[j];       }         if(b[j+1]==b[i])         {             f[i]=j+1;         }         else         {             f[i]=-1;         }     }  } int kmp() {     int sum=0;     int i=0;     int j=0;     int k=strlen(a);     int m=strlen(b);     while(i<k)     {         if(a[i]==b[j])         {             i++;             j++;             if(j==m)             {                 sum++;               }         }         else         {                 if(j==0)                 {                     i++;                 }                 else                 {                     j=0;                 }          }     }     return sum; } int main() {  //   int t; //   scanf("%d",&t);     while(1)    {       scanf(" %s",a);     if(a[0]=='#')     {         break;     }     scanf(" %s",b);      //memset(f,0,sizeof(f));         fc();        printf("%dn",kmp());    }     return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[2000005],a[2000005],c[2000005]; int f[2000005];  void fc(int l) {         int    j=-1;     f[0]=-1;   for(int i=0;i<l;)     {         if(j==-1||b[j]==b[i])//此时f表示达到另一个重复节之前的个数         {           f[++i]=++j;         }         else             {                 j=f[j];             }     }  } //int kmp() //{ //    int sum=0; //    int i=0; //    int j=0; //    int k=strlen(a); //    int m=strlen(b); //    while(i<k) //    { //        if(a[i]==b[j]) //        { //            i++; //            j++; //            if(j==m) //            { //                sum++; // // //            } //        } //        else //        { //                if(j==0) //                { //                    i++; //                } //                else //                { //                    j=int k=strlen(a);0; //                } // //        } //    } //    return sum; //} int main() {     int t;    scanf("%d",&t);     while(t--)    {       scanf(" %s",b);     int k=strlen(b); //    for(int i=0;i<k;i++) //    { //        b[i]=a[i]; //        a[i+k]=a[i]; //    } //    if(a[0]=='#') //    { //        break; //    } //    scanf(" %s",b);      //memset(f,0,sizeof(f));         fc(k);        int le=k-f[k];        if(le!=k&&k%le==0)        {          printf("0n");        }         else printf("%dn",le-k%le);    }     return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[2000005],a[2000005],c[2000005]; int f[2000005]; int m,n; void fc(int l) {      f[0]=f[1]=-1;     for(int i=1;i<l;i++)     {         //其实还是指针         int j=f[i];//j表示连续重复个数         while(j!=-1&&b[i]!=b[j+1])         {             j=f[j+1];          }         if(b[i]==b[j+1])         {              f[i+1]=j+1;         }          else         {             f[i+1]=-1;         }       }  } int kmp() {  }  int main() {     int w=1;   while(1)   {        scanf("%d",&n);       if(n==0)       {           break;       }     scanf(" %s",b);      fc(n);      printf("Test case #%dn",w++);     // w++;     for(int i=2;i<=n;i++)     {         int _length=i-f[i]-1;//最小循环节         if(f[i]>-1&&(i%_length==0))         printf("%d %dn",i,i/_length);      }     printf("n");   }       return 0; }  ```cpp #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[2000005],a[2000005],c[2000005]; int f[2000005]; int m,n; void fc(int l) {      f[0]=f[1]=-1;     for(int i=1;i<l;i++)     {         //其实还是指针         int j=f[i];//j表示连续重复个数         while(j!=-1&&b[i]!=b[j+1])         {             j=f[j+1];          }         if(b[i]==b[j+1])         {              f[i+1]=j+1;         }          else         {             f[i+1]=-1;         }       }  } int kmp() {  }  int main() {    // int w=1;   while( scanf(" %s",b)==1)   {        int k;       if(b[0]=='.')       {           break;       }       k=strlen(b);         fc(k);       int _length=k-f[k]-1;       if(f[k]>-1&&(k%_length==0))       {           printf("%dn",k/_length);       }       else       {           printf("1n");       }     // printf("Test case #%dn",w++);     // w++; //    for(int i=2;i<=n;i++) //    { //        int _length=i-f[i]-1;//最小循环节 //        if(f[i]>-1&&(i%_length==0)) //        printf("%d %dn",i,i/_length); // //    }   //  printf("n");   }       return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; char b[2000005],a[2000005],c[2000005]; int f[2000005]; int m,n; void fc(int l) {     int i=0;     int j=-1;     f[0]=-1;     while(i<=l)//循环节大小和一些规律都在其中     {         if(j==-1||b[j]==b[i])         {             f[++i]=++j;         }         else         {             j=f[j];         }      }    } int kmp() {  } vector<int> q; int main() {     while(scanf(" %s",b)!=EOF)     {         int k=strlen(b);         fc(k);         while(k>0)         {             q.push_back(k);             k=f[k];          }         int l=q.size();         for(int i=l-1;i>=0;i--)         {             printf("%d ",q[i]);         }         printf("n");         q.clear();       }        return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; int f[200005]; char d[15][65],*kk; int m,n; void fc(char *p ,int l)                                                    //这里数组传参char和string有区别string传参内容不会变而char会变  传参都是传的地址 {      int i=0;     int j=-1;     f[0]=-1;     while(i<l)     {         if(j==-1||p[i]==p[j])         {             f[++i]=++j;         }         else         {             j=f[j];         }      }   } bool kmp(char *p1,int l1,char *p2,int l2) {                                                             //printf("%sn",p2);     int i=0;     int j=0;     while(i<l1)     {         if(j==-1||p1[i]==p2[j])         {              ++i;             ++j;          }         else         {             j=f[j];          }         if(j==l2)         {                                                        //    printf("n  yes n");             return true;         }      }      return false; }                                                                     //vector<int> q;  int main() {                                                         //ios::sync_with_stdio(false);取消同步加速cout cin。但此处我使用麻烦的scanf  cin.tie(0);       int t;       int w;        scanf("%d",&t);     while(t--)     {                    memset(d,'',sizeof(d));         scanf("%d",&w);         for(int i=0;i<w;i++)         {             scanf("%s",d[i]);         }         char ans[65],*hh;                   memset(ans,'',sizeof(ans));         int lo=strlen(d[0]);         for(int i=0;i<lo;i++)         {             for(int j=1;i+j<=lo;j++)             {                 char res[65];                              memset(res,'',sizeof(res));                 for(int ii=0;ii<j;ii++)                 {                     res[ii]=d[0][ii+i];                 }                                                                        //复制字串从i开始                 hh=res;              int    ppo=strlen(res);                 fc(hh,ppo);                  bool flag=false;                                                                     //printf("%d",flag);                 for(int k=1;k<w;k++)                  {                      kk=d[k];                      int opo=strlen(d[k]);                    if(!kmp(kk,opo,res,ppo))                       {                           flag=true;                                                                    //                                             break;                                                                    //  printf("nnnnnnnnnooooooon");                       }                  }                                                                  //printf("%d",flag);                 if(!flag)                         {                             int iiop=strlen(ans);                                                                           //   printf(" *** %d  ***n   ",ppo);                         if(iiop<ppo)                         {                                 for(int pp=0;pp<ppo;pp++)                              {                                 ans[pp]=res[pp];                              }                         }                         else if(iiop==ppo)                         {                                                                       //printf("n %d n",iiop);                                 if(strcmp(ans,res)>0)                             {                                     for(int pp=0;pp<ppo;pp++)                               {                                 ans[pp]=res[pp];                                }                             }                         }                        }                 }               memset(f,'',sizeof(f));                                            // printf( " ********* %d   ********",iiop);         }         if(strlen(ans)<3)         {             printf("no significant commonalitiesn");         }         else         {             for(int i=0;i<strlen(ans);i++)             {                 printf("%c",ans[i]);             }             printf("n");         }      }     return 0; } 
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<vector> #include<map> #include<stack> #include<list> #include<set> #include<queue> #include<string> #include<string.h> using namespace std; //char a[500005]; //char b[500005]; //int f[500005]; //void fc(int l) //{ //    int i=0; //    int j=-1; //    f[0]=-1; //    while(i<l) //    { //        if(j==-1||a[i]==a[j]) //        { //            f[++i]=++j; // //        } //        else //        { //            j=f[j]; //        } // //    } //} //int kmp(int l) //{ //    int j=-1; //    for(int i=0;i<l;i++) //    { //        while (j>=0&&b[i]!=a[j+1]) //        { //            j=f[j]; //        } //        if(b[i]==a[j+1]) //        { //            j++; //        } //        if(i==l-1) //            return j; //    } //    return 0; //} //int main() //{ //    while(scanf("%s%s",a,b)!=EOF) //    { //        int q=strlen(a); //        int p=strlen(b); //        fc(q); //        int w=kmp(p)+1; //         if(w!=0) //            for(int i=0;i<w;i++) //         { //             printf("%c",a[i]); // //         } //         if(w==0) //            printf("0n"); //         else //         printf(" %dn",w); // // // // // //        memset(a,'',sizeof(a)); //        memset(b,'',sizeof(b)); //        memset(f,0,sizeof(f)); //    } // //    return 0; //} char a[500005],b[500005]; char c[1000010]; int f[1000010]; void fc(int l) {     int i=0;     int j=-1;     f[0]=-1;     while(i<l)     {         if(j==-1||c[i]==c[j])         {             f[++i]=++j;         }         else         {             j=f[j];         }     }  } int main() {     while(scanf("%s%s",a,b)!=EOF)     {          int q=strlen(a);         int p=strlen(b);          for(int i=0;i<q;i++)         {             c[i]=a[i];         }          for(int i=q;i<p+q;i++)         {             c[i]=b[i-q];         }         int k=strlen(c);        int y=min(q,p);       // printf("%d",y);         fc(k); //        for(int i=0;i<k;i++) //        { //            printf("%c",c[i]); //        }         if(f[k]>0)         {  if(f[k]<=y)            {             for(int j=0;j<f[k];j++)             printf("%c",c[j]);             printf(" %dn",f[k]);            }            else            {             for(int j=0;j<y;j++)             printf("%c",c[j]);             printf(" %dn",y);            }         }         else         {             printf("0n");         }           memset(a,'',sizeof(a));         memset(b,'',sizeof(b));         memset(c,'',sizeof(c));         memset(f,0,sizeof(f));     }      return 0; } 
#include <map> #include <set> #include <list> #include <queue> #include <deque> #include <cmath> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; char a[400000]; int b[400000]; int f[400000]; void fc(int l) {     int j=-1;     int i=0;     f[0]=-1;     while(i<l)     {         if(j==-1||a[i]==a[j])         {             f[++i]=++j;          }         else {             j=f[j];         }      } } int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         memset(b,0,sizeof(b));         scanf("%d",&n);         for(int i=0;i<n;i++)         {             scanf(" %c",&a[i]);         }         fc(n);         int ans=0;         for(int i=1;i<=n;i++)         {             b[f[i]]++;         }         for(int i=1;i<=n;i++)         {             if(b[i]>0)                 ans+=b[i];                 ans%=10007;                          }         ans+=n;         printf("%dn",ans%10007);         memset(f,0,sizeof(f));         memset(a,'',sizeof(a));     }     return 0; } 
#include <map> #include <set> #include <list> #include <queue> #include <deque> #include <cmath> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; char a[200000],c[200000]; int b[200000]; char mm[30],shadow[30]; int key[30],ip[30]; int f[200000]; void fc(int l,int k) {     int j=-1;     int i=k-1;     f[0]=-1;     while(i<l)     {         if(j==-1||a[i]==a[j])         {             f[++i]=++j;          }         else {             j=f[j];         }      } } int main() {     int t;     scanf("%d",&t);     while(t--)     {         scanf(" %s",mm);         for(int i=0;i<26;i++)         {             shadow[i]='a'+i;          //    printf("%c",shadow[i]);         }         for(int i=0;i<26;i++)         {             key[i]=mm[i]-'a';             ip[key[i]]=i;          }         scanf(" %s",a);         int k=strlen(a);         for(int i=0;i<k;i++)         {             b[i]=a[i]-'a';         }         int w=0;         int pp;         if(k%2==1)//优化         {             pp=k/2+1;         }         else         {             pp=k/2;         }         for(int i=0;i<pp;i++)         {                a[i]=ip[b[i]]+'a';                w++;         }         for(int i=pp;i<k;i++)         {              if(a[i]==a[0])             {                // printf("%d",f[k]);                 fc(k,pp);                 if(f[k]>0)                 {                      break;                 }             }              a[i]=ip[b[i]]+'a';             w++;          }         for(int i=0;i<w;i++)         {             printf("%c",b[i]+'a');         }          for(int i=0;i<w;i++)         {             printf("%c",a[i]);         }         printf("n");          memset(b,0,sizeof(b));         memset(f,0,sizeof(f));         memset(a,'',sizeof(a));     }     return 0; } 
#include <map> #include <set> #include <list> #include <queue> #include <deque> #include <cmath> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; char cw[105][105]; char ans[105]; int f[200]; void fc(char *p,int l) {     int j=-1;     int i=0;     f[0]=-1;     while(i<l)     {         if(j==-1||p[i]==p[j])         {             f[++i]=++j;          }         else {             j=f[j];         }      } } bool kmp(char *z ,int q,int p,int po) {      int j=-1;     for(int i=0;i<p;i++)     {         while(j!=-1&&cw[q][i]!=z[j+1])         {             j=f[j];         }         if(cw[q][i]==z[j+1])         {             j++;         }         if(j==po-1)         {             return true;         }     }     j=-1;     for(int i=p-1;i>=0;i--)     {         while(j!=-1&&cw[q][i]!=z[j+1])         {             j=f[j];         }         if(cw[q][i]==z[j+1])         {             j++;         }         if(j==po-1)         {              return true;         }     }     return false; } int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         scanf("%d",&n);     memset(cw,'',sizeof(cw));     memset(ans,'',sizeof(ans));     int pp[105];         for(int i=0;i<n;i++)          {              scanf(" %s",cw[i]);              pp[i]=strlen(cw[i]);              if(i==0)             for(int j=0;j<(int)strlen(cw[i]);j++)             {                 ans[j]=cw[i][j];             }             int aa=strlen(ans);             if(aa>pp[i])            {                 memset(ans,'',sizeof(ans));                for(int j=0;j<pp[i];j++)             {                 ans[j]=cw[i][j];             }            }          }          int k=strlen(ans);          int h=0;          for(int i=0;i<k;i++)          {              for(int j=1;j+i<=k;j++)              {                  char oo[105];                  for(int o=0;o<j;o++)                  {                      oo[o]=ans[o+i];                  }                //   printf("%sn",oo);                  char *l;                  l=oo;                  int ll=strlen(l);                  memset(f,-1,sizeof(f));                     fc(l,ll);                     bool flag=false;                  for(int ii=1;ii<n;ii++)                  {                       if(!kmp(l,ii,pp[i],ll))                       {                           flag=true;                       }                  }                  if(!flag)                   {                       h=max(h,j);                   }                   memset(oo,'',sizeof(oo));              }           }         printf("%dn",h);     }     return 0; } 

这其中我理解的kmp 是就好像指针的移动,我把next数组都简化为f数组 fc就是getnext(),在这里f数组的值前后缀匹配个数最大值和i-f[i]的值是循环节,都有特殊含义可以深入理解,利用到很多知识 ,其中由于stl学的太少了就在效率上面很吃亏。

本文地址https://www.b2bchain.cn/7393.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » kmp算法题全套svp版的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们