light oj 1255 - Substring Frequency (KMP)

举报
xindoo 发表于 2022/04/16 00:41:14 2022/04/16
【摘要】 题目链接 题意:       输入两个字符串,计算二串在一串中出现的次数。        裸裸的KMP,参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。 代码如下: //light oj 1255 - Substring Frequency ...

题目链接

题意:

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

      裸裸的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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。