HDOJ - 1586 更新下KMP的模板...

Program:

[cpp]
#include<iostream>  
#include<string>  
#include<cmath>  
#include<algorithm>  
#include<map>  
#include<set>  
#include<queue>  
#define ll long long   
#define oo 1000000000  
using namespace std;  
char s[2][1000005]; 
int _next[1000005]; 
int main() 
{ 
       int T,i,j,k,l0,l1,ans;  
       scanf("%d",&T); 
       while (T--) 
       { 
              scanf("%s%s",s[0]+1,s[1]+1); 
              l0=strlen(s[0]+1); 
              l1=strlen(s[1]+1); 
              memset(_next,0,sizeof(_next)); 
              s[0][l0+1]='#'; 
              for (i=2;i<=l0+1;i++) 
              { 
                    k=_next[i-1]; 
                    while (k && s[0][k]!=s[0][i-1]) k=_next[k];  
                    _next[i]=k+1; 
              } 
              k=ans=0;  
              for (i=1;i<=l1;i++) 
              {  
                    k++; 
                    while (k && s[0][k]!=s[1][i]) k=_next[k];  
                    if (k==l0) ans++;  
              } 
              printf("%d\n",ans); 
       } 
       return 0; 
}