light oj 1255 - Substring Frequency (KMP)

题目链接

题意：

      输入两个字符串，计算二串在一串中出现的次数。 

      裸裸的KMP，参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。

代码如下：

      //light oj 1255 - Substring Frequency (KMP)
      //2013-05-13-19.12
      #include <stdio.h>
      #include <string.h>
      const int maxn = 1000006;
      char a[maxn];
      char b[maxn];
      int f[maxn];
      void getfail()
      {
         int l = strlen(b);
          f[0] = 0;
          f[1] = 0;
         for (int i = 1; i < l; i++)
          {
             int j = f[i];
             while (j && b[i] != b[j])
                  j = f[j];
             if (b[i] == b[j])
                  f[i+1] = j+1;
             else
                  f[i+1] = 0;
          }
      }
      int kmp()
      {
         int ans = 0;
         int la = strlen(a);
         int lb = strlen(b);
         getfail();
         int j = 0;
         for (int i = 0; i < la; i++)
          {
             while (j && a[i] != b[j])
                  j = f[j];
             if (b[j] == a[i])
                  j++;
             if (j == lb)
                  ans++;
          }
         return ans;
      }
      int main()
      {
         int t;
         scanf("%d", &t);
         for (int i = 1; i <= t; i++)
          {
             scanf("%s %s", a, b);
             printf("Case %d: %d\n", i, kmp());
          }
         return 0;
      }
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8922076