Tag-KMP

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-04-05 22:47:29 |  0 Comments  |  字符串 KMP

POJ3461Oulipo -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;
}

 

Title - Artist
0:00