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