HDU 2087-剪花布条

灰太狼 2022-09-22 13:52 189阅读 0赞

HDU 2087

KMP算法

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using  namespace std;
  5. char a[1001],b[1001];
  6. int nextd[1001];
  7. void gnext()
  8. {
  9.     int l1=strlen(a+1);
  10.     int l2=strlen(b+1);
  11.     int s=1,t=0;
  12.     while(s<=l2)
  13.     {
  14.         if(t==0||b[s]==b[t])
  15.         {
  16.             t++;
  17.             nextd[++s]=t;
  18.         }
  19.         else
  20.         t=nextd[t];
  21.     }
  22. }
  23. int  kmpd()
  24. {
  25.     int l1=strlen(a+1);
  26.     int l2=strlen(b+1);
  27.     int cnt=0;
  28.     int s=1,t=1;
  29.     while(s<=l1)
  30.     {
  31.         if(t==0||a[s]==b[t])
  32.         {
  33.             t++;
  34.             s++;
  35.             if(t==l2+1)
  36.             { 
  37.                 cnt++;
  38.                 s+=l2-1;
  39.             }
  40.         }
  41.         else
  42.         t=nextd[t];
  43.     }
  44.     return cnt;
  45. }
  46. int main()
  47. {
  48.     int i,j,k,n,m,l1,l2,l;
  49.     while(~scanf("%s",a+1))
  50.     {
  51.         l1=strlen(a+1);
  52.         if(l1==1&&a[1]=='#')
  53.             break;
  54.         scanf("%s",b+1);
  55.         l2=strlen(b+1);
  56.         gnext();
  57.         printf("%d\n",kmpd());
  58.     }
  59.     return 0;
  60. }

发表评论

表情：
评论列表 （有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读