HDU 2087 剪花布条 KMP

KMP匹配数——

 
#include <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
using namespace std;  
  
typedef long long LL;  
const int N=1005;  
const LL II=100000000;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
int next[N],len,nextval[N];  
char str[N],xh[N];  
  
void getnext(char *p)  
{  
    int j=0,k=-1;  
    next[0]=-1;  
    while(j<len)//len是p的长度   
    {  
        if(k==-1||p[j]==p[k])  
        {  
            j++;    k++;  
            next[j]=k;  
        }  
        else  
            k=next[k];  
    }  
}  
  
void getnextval(const char *p)  
{  
    int i = 0,j =-1;  
    nextval[0]=-1;  
    while(i!=len)  
    {  
        if(j==-1||p[i]==p[j])  
        {  
            ++i;++j;  
            if(p[i]!=p[j])  
                nextval[i]=j;  
            else  
                nextval[i]=nextval[j];  
        }  
        else  
            j=nextval[j];  
    }  
}  
  
int kmp(char *text,char *word)  
{  
    int i=0,j=0,k=0,wlen=strlen(word);  
    while(i<len)//i指向text，j指向word   
    {  
        if(text[i]==word[j])  
        {       i++;j++;        }  
        else  
        {  
            j=next[j];      // 当j=0时，next[j]=-1   
            if(j==-1)  
            {       i++;     j=0;     }  
        }  
        if(j==wlen)   {k++;j=0;}  
    }  
    return k;  
}  
  
int main()  
{  
    int i,j,T;  
    while(scanf("%s",str)&&strcmp(str,"#")!=0)  
    {  
        scanf("%s",xh);  
        len=strlen(str);  
        getnext(str);  
        cout<<kmp(str,xh)<<endl;  
    }  
    return 0;  
}  

AC代码：

补充：软件开发 , C++ ,

上一个：POJ 1947 - Rebuilding Roads 树型DP(泛化背包转移)..
下一个：TC SRM 585