icontofig | 发布于 2019-04-05 22:47:29 | 阅读量 340 | 字符串 KMP
发布于 2019-04-05 22:47:29 | 字符串 KMP

 

 

不解释,就是KMP模板题……给出个人常用KMP模板QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
    int j = -1;
    nxt[0] = -1;
    for(int i = 1;i < s1.size();++i){
        while(j != -1 && s1[j+1] != s1[i])
            j = nxt[j];
        if(s1[j+1] == s1[i]){
            j++;
            nxt[i] = j;
        }
        else nxt[i] = -1;
    }
    return;
}
void KMP(){
    int j = -1; 
    cnt = 0;
    for(int i = 0;i < s2.size();++i){
        while(j != -1 && s1[j+1] != s2[i])
            j = nxt[j];
        if(s1[j+1] == s2[i])j++;
        if(j == s1.size()-1){
            cnt++;
            j = nxt[j];
        }
    }
    return;
}
int main(){
    cin >> n;
    while(n--){
        cin >> s1;
        cin >> s2;
        KMP_pre();
        KMP();
        cout << cnt << endl;
    }
    return 0;
}

 


内容更新于: 2019-04-05 23:23:33
链接地址: http://blog.leanote.com/post/icontofig/122c8e475a93

上一篇: poj - IMMEDIATE DECODABILITY Trie树模板

下一篇: UvaLive-6437 Power Plant(变种Kruskal)

340 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航