KMP 学习记录

kuangbin专题十六——KMP

KMP 学习总结

朴素 KMP 算法

void getNext(const char s[]){
    int cur = 0, k = -1;
    nxt[cur] = k;
    while (cur < m) {
        if (k == -1 || b[cur] == b[k])
            nxt[++cur] = ++k;
        else k = nxt[k];
    }
}

int kmp(const char a[], const char b[]){
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || a[i] == b[j]) ++i, ++j;
        else j = nxt[j];
        if (j == m) return i;
    }
    return -1;
}

拓展 KMP 算法

void getNext(const char T[]){
    int len=strlen(T), a=0;
    nxt[0] = len;
    while(a<len-1 && T[a]==T[a+1]) ++a;
    nxt[1] = a;
    a=1;
    for(int k=2; k<len; ++k){
        int p=a+nxt[a]-1, L=nxt[k-a];
        if(k-1+L >= p){
            int j = (p-k+1)>0?(p-k+1):0;
            while(k+j<len && T[k+j]==T[j]) ++j;
            nxt[k] = j;
            a=k;
        }
        else
            nxt[k]=L;
    }
}

void getExtend(const char S[],const char T[]){
    getNext(T);
    int slen = strlen(S), tlen = strlen(T), a = 0;
    int minLen = min(slen, tlen);
    while(a<minLen && S[a]==T[a]) ++a;
    extend[0] = a;
    a=0;
    for(int k=1; k<slen; ++k){
        int p = a+extend[a]-1, L = nxt[k-a];
        if(k-1+L >= p){
            int j = max(p-k+1, 0);
            while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;
            extend[k] = j;
            a=k;
        }
        else
            extend[k] = L;
    }
}

HDU 1711

Number Sequence

题意

给出t组样例和两串数列,在a串中求出b串所在位置。

思路

KMP裸题,根据b串求出匹配序列next之后依次匹配即可。

代码

#include <cstdio>
using namespace std;
#define LOCAL
const int maxn = 1e6+7;
int a[maxn], b[maxn], next[maxn], n, m;
void getNext(){
    int cur = 0, k = -1;
    next[cur] = k;
    while (cur < m) {
        if (k == -1 || b[cur] == b[k])
            next[++cur] = ++k;
        else k = next[k];
    }
}
int kmp(){
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || a[i] == b[j]) ++i, ++j;
        else j = next[j];
        if (j == m) return i;
    }
    return -1;
}
int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i)
            scanf("%d", a+i);
        for (int i = 0; i < m; ++i)
            scanf("%d", b+i);
        getNext();
        if (kmp()==-1)
            printf("-1\n");
        else
            printf("%d\n", kmp()-m+1);
    }
    return 0;
}

HDU 1686

Oulipo

题意

给出t组样例,每组样例有两个字符串。要求在b串中能找到多少个a串,每个a串有可能重叠。

思路

简单KMP。由于对KMP理解不深,在匹配的时候选择了回到开始位置,这样会导致重复匹配,可以回到结尾位置对应的前缀位置,这样可以提高效率。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
//#define LOCAL

int cas, nxt[10005], m, n;
char s[10005];
char t[1000007];

void getNext() {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while(cur < m) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else k = nxt[k];
    }
}

int kmp() {
    int i = 0, j = 0, ans = 0;
    while (i < n) {
        if (j == -1 || t[i] == s[j]) ++i, ++j;
        else j = nxt[j];
        if (j == m) {
            ++ans;
            j = nxt[j];
        }
    }
    return ans;
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &cas);
    while (cas--) {
        scanf("%s%s", s, t);
        m = strlen(s), n = strlen(t);
        getNext();
        printf("%d\n", kmp());
    }
    return 0;
}

HDU 2087

题意

有多组样例,读入到#时终止。每组样例有两个字符串,求能在a串中找到多少个b串。

思路

KMP匹配即可,匹配完成之后小串指针归零。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
#define LOCAL

char a[1005], b[1005];
int m, n, nxt[1005];

void getNext(){
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (cur < m) {
        if (k == -1 || b[cur] == b[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}

int kmp(){
    int i = 0, j = 0, cnt = 0;
    while (i < n) {
        if (j == -1 || a[i] == b[j]){
            ++i, ++j;
        }
        else j = nxt[j];
        if (j == m)
            ++cnt, j = 0;
    }
    return cnt;
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    while (~scanf("%s", a) && a[0] != '#') {
        scanf("%s", b);
        n = strlen(a), m = strlen(b);
        getNext();
        printf("%d\n", kmp());
    }
    return 0;
}

HDU 3746

Cyclic Nacklace

题意

t组样例。每组样例给出一个字符串,要求要在两端补上多少个字符才能让其变为多个完全相同的字符串合并成的字符串。

思路

KMP。根据题意发现,两端添加字符其实和一端是一样的。
那么我们只要根据匹配序列,获得字符串尾端的最长公共前后缀长度nxt[len],这样可以求出最短的子序列长度为xlen = len-nxt[len]。如果len%xlen==0那么这个字符串本身就已经是多个相同的字符串组合而成的了,否则的话,需要增添的字符数量就是xlen-nxt[len]%xlen

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
#define LOCAL

char s[100007];
int m, n, nxt[100007];

void getNext(){
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (cur < m) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}
int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        m = strlen(s);
        getNext();
        n = m - nxt[m];
        if (n != m && !(m%n))
            printf("0\n");
        else
            printf("%d\n", n - nxt[m]%n);
    }
    return 0;
}

HDU 1358

题意

有多组样例,读到0时结束。每组样例是一个字符串,要求字符串的每个长度大于二的子串是否是一个由不少于一个相同的字符串连接成的串。

思路

一开始想了很久,后来才知道这居然是一个性质:i%(i-next[i])==0,那么这个长度为i的串就是一个重复串,并且循环节长度为i-next[i]

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
#define LOCAL

int nxt[1000007], n;
char s[1000007];

void getNext() {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (cur < n) {
        if (k == -1 || s[cur] == s[k]){
            nxt[++cur] = ++k;
        }
        else k = nxt[k];
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int cas = 0;
    while (scanf("%d", &n), n) {
        scanf("%s", s);
        getNext();
        printf("Test case #%d\n", ++cas);
        for (int i = 2; i <= n; ++i){
            if (i%(i-nxt[i]) == 0 && nxt[i])
                printf("%d %d\n", i, i/(i-nxt[i]));
        }
        printf("\n");
    }
    return 0;
}

POJ 3080

Blue Jeans

题意

给出多个长度为60的字符串,求出字典序最大的最长公共子串。

思路

因为数据范围不大,所以暴力枚举第一个串的所有子串,然后KMP匹配即可。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
#define LOCAL

char s[12][67], ans[67], now[67];
int nxt[67], len, len_ans, flag;

void getNext(const char s[]) {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (s[cur]) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}

int kmp(const char s[]) {
    int i = 0, j = 0;
    while (s[i]) {
        if (j == -1 || s[i] == now[j]) ++i, ++j;
        else j = nxt[j];
        if (j == len) return 1;
    }
    return 0;
}

bool check() {
    //printf("_%s %s\n", ans, now);
    if (len > len_ans) return true;
    int cur = -1;
    return strcmp(ans, now) > 0;
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--) {
        int m; scanf("%d", &m);
        for (int i = 0; i < m; ++i)
            scanf("%s", s[i]);
        for (len = 1, len_ans = 0; len <= 60; ++len) {
            for (int cur = 0, flag = 1; cur <= 60-len; ++cur, flag = 1) {
                for (int i = 0; i < len; ++i)
                    now[i] = s[0][cur+i];
                now[len] = '\0';
                getNext(now);
                for (int i = 1; i < m; ++i) if (!kmp(s[i])) {
                    flag = 0;
                    break;
                }
                if (flag && check()){
                    strcpy(ans, now);
                    len_ans = len;
                }
            }
        }
        if (len_ans < 3)
            printf("%s\n", "no significant commonalities");
        else
            printf("%s\n", ans);
    }
    return 0;
}

HDU 3336

Count the string

题意

给出一个字符串,求这个字符串的每个前缀在字符串中出现的次数总和。

思路

KMP。依然是考对next数组的理解程度。
next数组表示当前位置的最大公共前后缀长度,那么这个最大的公共前后缀长度中包含的就是前缀中的每个小前缀的数量。也就是说,next数组在这道题目中就可以用来表示当前位置的后缀中出现了的重复前缀数量,可以直接加入计数器当中。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
const int mod = 10007;

int n, nxt[200007];
char s[200007];

void getNext() {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (s[cur]) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%s", &n, s);
        getNext();
        int ans = (nxt[n] + n)%mod;
        for (int i = 0; i < n; ++i)
            if (nxt[i] && nxt[i+1] != nxt[i]+1)
                ans += nxt[i];
        printf("%d\n", ans%mod);
    }
    return 0;
}

HDU 4300

Clairewd’s message

题意

给出若干样例,每个样例有两个字符串。第一个字符串是26个英文字母对应的密码表,第二个字符串是密文和明文连接成的,其中的明文可能不全,可能没有。求补完明文串。

思路

  1. 数据较弱,可以暴力。

  2. 用朴素KMP完成,将字符串的前一半翻译为明文,后一半不变,然后生成next数组,看最后一位的大小就知道密文的长度。

  3. 用拓展KMP完成,将字符串整个翻译为明文,原串为模式串,新串为主串,生成extend,遍历extend找第一个完全匹配的点(这个点后面的字符都能和主串的前缀匹配),就知道密文的长度了。

代码

\\ 朴素KMP
#include <cstdio>
using namespace std;

char a[27];
char s1[100007];
char s2[100007];
int nxt[100007];

void getNext(char s[]) {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (s[cur]) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s%s", a+1, s1);
        char b[27];
        for (int i = 1; i <= 26; ++i)
            b[a[i]-'a'] = i+'a'-1;
        int len = strlen(s1);
        int k = len;
        for (int i = 0; i < (len+1)>>1; ++i)
            s2[i] = b[s1[i]-'a'];
        for (int i = (len+1)>>1; i <= len; ++i)
            s2[i] = s1[i];
        getNext(s2);
        while (nxt[k] > len>>1)
            k = nxt[k];
        printf(s1);
        for (int i = nxt[k]; i < len-nxt[k]; ++i)
            printf("%c", b[s1[i]-'a']);
        printf("\n");
    }
    return 0;
}

\\ 拓展KMP
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 100000+7;

char s1[maxn], s2[maxn];
int nxt[maxn], extend[maxn];

void getNext(const char T[]){
    int len=strlen(T), a=0;
    nxt[0] = len;
    while(a<len-1 && T[a]==T[a+1]) ++a;
    nxt[1] = a;
    a=1;
    for(int k=2; k<len; ++k){
        int p=a+nxt[a]-1, L=nxt[k-a];
        if(k-1+L >= p){
            int j = (p-k+1)>0?(p-k+1):0;
            while(k+j<len && T[k+j]==T[j]) ++j;
            nxt[k] = j;
            a=k;
        }
        else
            nxt[k]=L;
    }
}

void getExtend(const char S[],const char T[]){
    getNext(T);
    int slen = strlen(S), tlen = strlen(T), a = 0;
    int minLen = min(slen, tlen);
    while(a<minLen && S[a]==T[a]) ++a;
    extend[0] = a;
    a=0;
    for(int k=1; k<slen; ++k){
        int p = a+extend[a]-1, L = nxt[k-a];
        if(k-1+L >= p){
            int j = max(p-k+1, 0);
            while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;
            extend[k] = j;
            a=k;
        }
        else
            extend[k] = L;
    }
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--) {
        char table[30], b[200];
        scanf("%s%s", table, s1);
        for (int i = 0; table[i]; ++i)
            b[table[i]] = i+'a';
        for (int i = 0; s1[i]; ++i)
            s2[i] = b[s1[i]];
        getExtend(s1, s2);
        int n = strlen(s1), cur = n;
        for (int i = 0; s1[i]; ++i)
            if (i+extend[i] >= n && i >= extend[i]) {
                cur = i;
                break;
            }
        char ans[maxn*2];
        for (int i = 0; i < cur; ++i){
            ans[i] = s1[i];
            ans[cur+i] = s2[i];
        }
        ans[cur*2] = '\0';
        printf("%s\n", ans);
    }
    return 0;
}

HDU 2328

Corporate Identity

题意

找多个字符串的公共子串。

思路

暴力枚举+KMP,没什么好说的。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

int nxt[203], len, len_ans;
char s[4003][203], now[203], ans[203];

void getNext(const char s[]) {
    int cur = 0, k = -1;
    nxt[0] = -1;
    while (s[cur]) {
        if (k == -1 || s[cur] == s[k])
            nxt[++cur] = ++k;
        else
            k = nxt[k];
    }
}

int kmp(const char s[]) {
    int i = 0, j = 0;
    while (s[i]) {
        if (j == -1 || s[i] == now[j]) ++i, ++j;
        else j = nxt[j];
        if (j == len) return 1;
    }
    return 0;
}

bool check() {
    if (len > len_ans) return true;
    return strcmp(ans, now) > 0;
}

int main(){
    int n;
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; ++i)
            scanf("%s", s[i]);
        int mi = strlen(s[0]);
        for (len = 1, len_ans = 0; len <= mi; ++len) {
            for (int i = 0, flag = 1; i <= mi-len; ++i, flag = 1) {
                for (int j = 0; j < len; ++j)
                    now[j] = s[0][i+j];
                now[len] = '\0';
                getNext(now);
                for (int j = 1; j < n; ++j) if (!kmp(s[j])) {
                    flag = 0;
                    break;
                }
                if (flag && check()) {
                    strcpy(ans, now);
                    len_ans = len;
                }
            }
        }
        if (len_ans == 0)
            printf("IDENTITY LOST\n");
        else
            printf("%s\n", ans);
    }
    return 0;
}