目录

KMP

字符串匹配

最小循环覆盖 

EXKMP

字符串匹配

Secret word 

Password 

---

KMP

模板

void kmp() {
    int m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for (int i = 2; i <= m; ++i) {
        while (j && p[i] != p[j + 1])
            j = nxt[j];
        if (p[i] == p[j + 1])
            ++j;
        nxt[i] = j;
    }
}

p[i]  与  p[j + 1]  作比较？ 

j是与i - 1的字符相匹配的。所以但我们计算i时，待匹配的是j + 1 这个位置的字符。

比如下方的第二个和第四个字符，都是b，他们是匹配的。i等于5之后，此时的j还是2，所以是i与j+1进行比较。

用来解决字符串的匹配问题，比如在文档中  Ctrl + F 去查找特定的内容。

需要清除nxt数组的含义:

                a        b        a        b        a        c        m

                0        0        1        2        3        0        0

nxt[i]  以i结尾的字符，与p字符串前缀最大匹配的长度

字符串匹配

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
 
char s[100005], p[100005];
int nxt[100005], f[100005];
int n, m;
void solve() {
 
    scanf("%s%s", s + 1, p + 1);
 
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
 
    for (int i = 2; i <= m; ++i) {
        while (j && p[i] != p[j + 1])
            j = nxt[j];
        if (p[i] == p[j + 1])
            ++j;
        nxt[i] = j;
    }
    
    j = 0;
    for (int i = 1; i <= n; ++i) {
        while (j == m || (j && s[i] != p[j + 1]))
            j = nxt[j];
        if (s[i] == p[j + 1])
            ++j;
        f[i] = j;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (f[i] == m)
            ans++;
    }
    if (ans == 0) printf("-1\n-1\n");
    else {
        printf("%d\n", ans);
        for (int i = 1; i <= n; ++i) {
            if (f[i] == m) {
                printf("%d ", i - m + 1);
            }
        }
        puts("");
    }
}
int main(){
    int t; scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        solve();
    }   
    return 0;
}

最小循环覆盖 

结论：m - nxt[m] 

nxt[m] 是以m为结尾的字符，与字符串p前缀匹配的最大长度。 

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
 
char p[100005];
int nxt[100005];
void kmp() {
    int m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for (int i = 2; i <= m; ++i) {
        while (j && p[i] != p[j + 1])
            j = nxt[j];
        if (p[i] == p[j + 1])
            ++j;
        nxt[i] = j;
    }
    printf("%d\n", m - nxt[m]);
}
int main(){
    scanf("%s", p + 1);
    kmp();
    return 0;
}

EXKMP

拓展kmp，又称Z算法

模板：

void exkmp() {
    int n = strlen(s + 1);
    z[1] = 0;
    int L = 1, R = 0;
    for (int i = 2; i <= n; ++i) {
        if (i > R) {
            z[i] = 0;
        } else {
            int k = i - L + 1;
            z[i] = min(z[k], R - i + 1);
        }
        while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > R) {
            L = i, R = i + z[i] - 1;
        }
    }
}

z[i]  ： 从i开始的字符串与s字符串前缀最大匹配的长度

字符串匹配

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 200005;
char s[N], p[N];
int z[N];
int n, m;
 
void solve() {
    scanf("%s%s", s + 1, p + 1);
    n = strlen(s + 1);
    m = strlen(p + 1);
    p[m + 1] = '#';
    for (int i = m + 2, j = 1; j <= n; ++i, ++j) {
        p[i] = s[j];
    }
    
    z[1] = 0;
    int L = 1, R = 0;
    for (int i = 2; i <= n + m + 1; ++i) {
        if (i > R) {
            z[i] = 0;
        } else {
            int k = i - L + 1;
            z[i] = min(z[k], R - i + 1);
        }
        while (i + z[i] <= n + m + 1 && p[z[i] + 1] == p[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > R) {
            L = i, R = i + z[i] - 1;
        }
    }
 
    int ans = 0;
    for (int i = m + 2; i <= n + m + 1; ++i) {
        if (z[i] == m) ans++;
    }
    if (ans == 0) puts("-1\n-1");
    else {
        printf("%d\n", ans);
        for (int i = m + 2; i <= n + m + 1; ++i) {
            if (z[i] == m) {
                printf("%d ", i - m - 1);
            }
        }
        puts("");
    }
}
int main(){
    int t; scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

Secret word 

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
 
const int N = 1E5 + 5;
char s[N << 1];
int z[N << 1];
 
void solve() {
    int n = strlen(s + 1);
    s[n + 1] = '#';
 
    for (int i = n + 2, j = n; j ; --j, ++i) {
        s[i] = s[j];
    }
 
    z[1] = 0;
    int L = 1, R = 0;
    for (int i = 2; i <= 2 * n + 1; ++i) {
        if (i > R) {
            z[i] = 0;
        } else {
            int k = i - L + 1;
            z[i] = min(z[k], R - i + 1);
        }
        while (i + z[i] <= 2 * n + 1 && s[z[i] + 1] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > R) {
            L = i, R = i + z[i] - 1;
        }
    }
    int ans = 0;
    for (int i = n + 2; i <= 2 * n + 1; ++i) {
        ans = max(ans, z[i]);
    }
    for (int i = ans; i >= 1; --i)
        printf("%c", s[i]);
    putchar(10);
}
int main(){
    scanf("%s", s + 1);
    solve();
 
    return 0;
}

Password 

#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 1000005;
char s[N], p[N];
int z[N];
int n, m;
 
void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    
    z[1] = 0;
    int L = 1, R = 0;
    for (int i = 2; i <= n; ++i) {
        if (i > R) {
            z[i] = 0;
        } else {
            int k = i - L + 1;
            z[i] = min(z[k], R - i + 1);
        }
        while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > R) {
            L = i, R = i + z[i] - 1;
        }
    }
 
    int ans = 0, x = 0;
    for (int i = 1; i <= n; ++i) {
        if (z[i] == n - i + 1) {
            if (x >= z[i])
                ans = max(ans, z[i]);
        }
        x = max(x, z[i]);
    }
    if (!ans) printf("Just a legend\n");
    else {
        for (int i = 1; i <= ans; ++i)
            printf("%c", s[i]);
        puts("");
    }
}
int main(){
    solve();
    return 0;
}