KMP算法解题模板（更新）

/*

kmp算法的主要作用在于对next数组的运用，所以这里只给出next数组的模板

性质1：对于每一个长度len的子串，该子串的最小循环节为len-next[len]

性质2：kmp的next不断向前递归的过程可以保证对于每一个当前前缀，都有一段后缀与之对应

*/

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e6+5;

int Next[maxn];

char mo[maxn];

int n2;

void GetNext() {

    int i = 0, j = -1;

    while (i < n2) {

        if(j == -1 || mo[i] == mo[j]) {

            i++;

            j++;

            Next[i] = j;

        } else j = Next[j];

    }

    return;

}

int main() {

    cin >> mo;

    n2 = strlen(mo);

    Next[0] = -1;

    GetNext();

    return 0;

}

/*

kmp模板

题意就是求B串在A串中的第一次匹配的下标，（从1开始）

str就是A,mo就是B

*/

#include<bits/stdc++.h>

using namespace std ;

const int maxn = 1e6+5;

int Next[maxn], n1, n2;

char str[maxn], mo[maxn];

void GetNext() {

    int i = 0, j = -1;

    while(i < n2) {

        if(j == -1 || mo[i] == mo[j]) {

            i++;

            j++;

            Next[i] = j;

        } else j = Next[j];

    }

    return;

}

int kmp() {

    int cnt = 0;

    int i = 0, j = 0;

    while(i < n1) {

        if(j == -1 || str[i] == mo[j]) {

            i++;

            j++;

        } else j = Next[j];              //next数组寻找与当前后缀匹配最长的前缀，省略不必要的查找

        if(j == n2) return i - n2 + 1;   //首地址

    }

    return -1;

}

int main() {

    cin >> str >> mo;

    n1 = strlen(str);

    n2 = strlen(mo);

    Next[0] = -1;

    GetNext();

    cout << kmp() << endl;

    return 0;

}

/*

kmp模板

题意就是求B串在A串中的出现次数（可重叠

str就是S,mo就是B

*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

int Next[maxn], n1, n2;

char str[maxn], mo[maxn];

void GetNext() {

    int i = 0, j = -1;

    while(i < n2) {

        if(j == -1 || mo[i] == mo[j]) {

            i++;

            j++;

            Next[i] = j;

        } else j = Next[j];

    }

    return;

}

int kmp() {

    int cnt = 0;

    int i = 0, j = 0;

    while(i < n1) {

        if (j == -1 || str[i] == mo[j]) {

            i++;

            j++;

        } else j = Next[j];

        if(j == n2) {

            cnt++;

            j=Next[j];      //完成一次匹配，将j移动到最长的前缀处，省略不必要的查找

        }

    }

    return cnt;

}

int main() {

    cin >> str >> mo;

    n1 = strlen(str);

    n2 = strlen(mo);

    Next[0] = -1;

    GetNext();

    cout << kmp() << endl;

    return 0;

}

/*

kmp模板

题意就是求B串在A串中的出现次数（不可重叠

str就是A,mo就是B

*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

int Next[maxn], n1, n2;

char str[maxn], mo[maxn];

void GetNext() {

    int i = 0, j = -1;

    while (i < n2) {

        if (j == -1 || mo[i] == mo[j]) {

            i++;

            j++;

            Next[i] = j;

        } else j = Next[j];

    }

    return;

}

int kmp() {

    int cnt = 0;

    int i = 0, j = 0;

    while (i < n1) {

        if (j == -1 || str[i] == mo[j]) {

            i++;

            j++;

        } else j = Next[j];

        if (j == n2) {

            cnt++;

            j = 0;

        }

    }

    return cnt;

}

int main() {

    cin >> str >> mo;

    n1 = strlen(str);

    n2 = strlen(mo);

    Next[0] = -1;

    GetNext();

    cout << kmp() << endl;

    return 0;

}

/*

最小循环节 POJ 2406 Power Strings

结论：如果len%（len-nxt[len]）=0，那么循环次数为len/（len-nxt[len]），否则为1

*/

#include <cstdio>

#include <cstring>

using namespace std;

char s[1000100];

int nxt[1000100];

void get_nxt(){

    int len = strlen(s);

    nxt[0] = -1;

    int i = 0, j = -1;

    while (i < len){

        if (j == -1 || s[i] == s[j]){

            i++, j++;

            nxt[i] = j;

        }

        else j = nxt[j];

    }

}

int main(){

    //freopen("in.txt", "r", stdin);

    while (scanf("%s", s)){

        int len = strlen(s);

        if (len == 1 && s[0] == '.')break;

        get_nxt();

        int ans = len % (len - nxt[len]) == 0 ? len / (len - nxt[len]) : 1;

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

KMP算法解题模板（更新）

最新文章

热门文章