MP

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
/*
mp.in：
ABABABC
ABA 
*/ 
///////////////////////////////////
char te[1000000<<2],pa[1000<<2];
int lte,lpa;
int next[1000000<<2];
///////////////////////////////////
inline void in()
{
    scanf("%s",te+1);
    scanf("%s",pa+1);
    lte=strlen(te+1);
    lpa=strlen(pa+1);
}
///////////////////////////////////
int main()
{
    freopen("mp.in","r",stdin);
    in();
    for(int i=2;i<=lpa;i++)
      {
        int k=next[i-1];
        while(k>0&&pa[k+1]!=pa[i])
          k=next[k];
        if(pa[k+1]==pa[i])
          {
            k++;
            next[i]=k;
          }
      }
    int k=0;
    for(int i=1;i<=lte;i++)
      {
        while(k>0&&pa[k+1]!=te[i])
          k=next[k];
        if(pa[k+1]==te[i])
          k++;
        if(k==lpa)
          {
            cout<<i-lpa+1<<endl;
          }
      }
    for(int i=1;i<=lpa;i++)
      cout<<next[i]<<" ";
}

KMP

//poj2046 
//大意:给出一个字符串 问它最多由多少相同的字串组成 
//如:abababab由4个ab组成
//样例
/* 
abcd    对应next[]为 0 0 0 0  
aaaa    0 1 2 3 
ababab  0 0 1 2 3 4
. */ 
//答案 
//0 4 3 
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
/////////////////////////////
char a[1000010];
int la;
int next[1000010];
/////////////////////////////
void work()
{
    la=strlen(a+1);
    if(a[1]=='.')
      return ;
    int k=0;
    for(int i=2;i<=la;i++)
      {
        while(k>0&&a[k+1]!=a[i])
          k=next[k];
        if(a[k+1]==a[i])
          {
            k++;
            next[i]=k;
          }
      }
    for(int i=1;i<=la;i++)
      cout<<next[i]<<" ";
    if(!(la%(la-next[la])))
      cout<<la/(la-next[la])<<endl;
    else
      cout<<1<<endl;
    memset(a,0,sizeof(a));
    memset(next,0,sizeof(next));
}
/////////////////////////////
int main()
{
    freopen("poj2406.txt","r",stdin);
    //freopen("cqj.out","w",stdout);
    while(scanf("%s",a+1)!=EOF)
      {
        work();
      }
}

扩K（）

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
///////////////////////////////////
char text[10000],pa[10000];
int next[10000];
int lt,lp;
///////////////////////////////////

///////////////////////////////////
int main()
{
    freopen("kk.in","r",stdin);
    scanf("%s",pa+1);
    lp=strlen(pa+1);
    int a=0,p,l,j;
    while(a<lp&&(pa[a+1]==pa[a+2]))
      a++;
    next[1]=lp,next[2]=a;
    for(int k=3;k<=lp;k++)
      {
        p=a+next[a]-1;
        l=next[k-a+1];
        if(k+1-1>=p)
          {
            if(p-k+1>0)
              j=p-k+1;
            else
              j=0;
            while(k+j<=lp&&pa[k+j]==pa[j+1])
              j++;
            next[k]=j;
            a=k;
          }
        else
          next[k]=l;
      }
    for(int i=1;i<=lp;i++)
      cout<<i<<" "<<next[i]<<endl;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接