kmp的实现——简单算法

我就是我 2022-12-03 08:48 152阅读 0赞

#include <iostream>
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <string>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int maxn = 2005;
    #define eps 1e-8
    #define INIT(x) memset(x,0,sizeof(x))
    typedef long long ll;
    
    string s2,s1;
    int nxt[maxn];
    
    void get_next(string s)
    {
        
        nxt[0] = -1;
        nxt[1] = 0;
        int cn = 0;
        int i = 2;
        while(i<s.length())
        {
        
            if(s[i-1]==s[cn])
                nxt[i++] = ++cn;
            else if(cn>0)
                cn = nxt[cn];
            else
                nxt[i++] = 0;
        }
    }
    
    int kmp()
    {
        
        INIT(nxt);
        int ans = 0;
        get_next(s2);
        int i=0,j=0;
        while(i<s1.length()&&j<s2.length())
        {
        
            if(s1[i]==s2[j]) {
        
                i++,j++;
            }else if(nxt[j]==-1) {
        
                i++;
                j=0;
            }else {
        
                j = nxt[j];
            }
            if(j==s2.length()) {
        
                ans++;
                j = 0;
            }
        }
        return ans;
    }
    
    int main()
    {
        
        while(cin>>s1)
        {
        
            if(s1=="#") break;
            cin>>s2;
            int ans = kmp();
            cout<<ans<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

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

相关阅读

相关 KMP算法的简单理解

引入对于串的匹配，较为简单的有BF算法，但这种方法的可用性却较差。因为在每次不匹配的时候，主串（m位）和子串（n位）都会回溯,有一种最坏的情况就是，主串每前进一位，都在

「爱情、让人受尽委屈。」/ 2023年07月07日 08:17/ 0 赞/ 232 阅读

相关 KMP算法的实现（Java）

KMP算法的实现（Java） KMP算法 KMP算法的实现（Java）简介问题暴力算法（Brute Force）

「爱情、让人受尽委屈。」/ 2023年02月16日 12:26/ 0 赞/ 70 阅读

相关 kmp的实现——简单算法

include <iostream> include <cstdio> include <iostream> include <cstring>

我就是我/ 2022年12月03日 08:48/ 0 赞/ 153 阅读

相关用C语言实现KMP算法,KMP算法纯C实现

该楼层疑似违规已被系统折叠隐藏此楼查看此楼我自己写的KMP算法： int nt\[256\]; void get\_next1(char\ T, int next\[

清疚/ 2022年10月15日 15:57/ 0 赞/ 150 阅读

相关 KMP算法代码实现

有关KMP算法，这里有篇博客讲解的特别好，博客链接为： [http://blog.csdn.net/tukangzheng/article/details/38438481]

墨蓝/ 2022年08月05日 11:17/ 0 赞/ 190 阅读

相关 KMP算法的Java实现

输入第一行一个整数N，表示测试数据组数。接下来的N\2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，

灰太狼/ 2022年06月12日 04:40/ 0 赞/ 166 阅读

相关 KMP算法实现Python/Java

kmp算法的核心时间复杂度就是O（m+n）参考原理： [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%9

骑猪看日落/ 2022年05月29日 04:14/ 0 赞/ 156 阅读

相关 KMP java实现【算法】

package com.using.test; import org.junit.Test; public class KMPTes

谁借莪１个温暖的怀抱￠/ 2022年05月13日 03:40/ 0 赞/ 163 阅读

相关最简单的方法理解KMP算法

KMP算法 > 在求解字符串的匹配问题时，最容易让人想到的便是BF算法，但是由于BF的时间复杂度为O(n\m)，所以并不是很好。而KMP算法同样用于求解字符

痛定思痛。/ 2021年09月20日 10:00/ 0 赞/ 347 阅读

相关 KMP算法实现字符串匹配

一需求 1 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"。 2 现在要判断 str1 是否含

以你之姓@/ 2021年07月24日 23:06/ 0 赞/ 443 阅读