hdu2087kmp模板练习

题目网址：http://icpc.njust.edu.cn/Problem/Hdu/2087/

代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 100010

 int n,m,t;

 char s[maxn],p[maxn],nxt[maxn];

 void getnxt()

 {

     int plen=strlen(p);

     int i=-,j=;

     nxt[]=-;

     while(j<plen)

     {

         if(i==-||p[i]==p[j])

         {

             i++,j++;

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

             else nxt[j]=i;

         }

         else i=nxt[i];

     }

 }

 int kmp()

 {

     int plen=strlen(p);

     int slen=strlen(s);

     int j=,i=;

     int cnt=;

     while(i<slen)

     {

         if(j==-||s[i]==p[j])i++,j++;

         else j=nxt[j];

         if(j==plen)

         {

             j=,cnt++;

         }

     }

     return cnt;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

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

     {

         if(!strcmp(s,"#"))break;

         scanf(" %s",p);

         getnxt();

         pf("%d\n",kmp());

     }

  }