KMP 技巧

ademik · 2023-02-01 18:26:23 · 个人记录

依照 oi-wiki 上的文段所言，KMP问题基于前缀函数。
本文就以此给出自己的理解与具体实现代码

• KMP模板 (luogu P3370)

using namespace std;
const int N = 1e6 + 50;
char a[N], b[N];
int p[N]; // 即next，记录前j个字符中的 最长的相同的前缀和后缀
int main()
{
    cin >>(a + 1) >>(b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    int j = 0; p[1] = 0;
    for(int i = 2; i <= m; i ++) {
        while(j > 0 && b[j + 1] != b[i]) j = p[j];
        if(b[j + 1] == b[i]) j ++;
        p[i] = j;
    }
    j = 0; 
    for(int i = 1; i <= n; i ++) {
        while(j > 0 && b[j + 1] != a[i]) j = p[j];
        if(b[j + 1] == a[i]) j ++;
        if(j == m) {cout <<i - m + 1 <<endl; j = p[j];}
    }
    for(int i = 1; i <= m; i ++) cout <<p[i] <<" ";
    return 0;
}

• 字符串的周期 (luogu P3435)

  • 字符串的周期与数学上的周期类似，即对于 \forall i \in [1, |s| - p - 1]， 满足s[i] = s[i + T].
  • 我们已知 s 的 border 长度为 r , 若 border > 0， |s| - r 一定是s的一个周期(例如: abcdab，r = 2, T = 4)
  • 对于例题中所求的最大周期, 由于字串的长度i恒定， T = i - j(boder的长度)， 故而求最小的j满足j>0即可

using namespace std;
const int N = 1e6 + 60;
char a[N]; int n, p[N]; long long ans;
int main() 
{
    cin >>n >>(a + 1);
    int j = 0;
    for(int i = 2; i <= n; i ++) {
        while(j > 0 && (a[j + 1] != a[i])) j = p[j];
        j += (a[j + 1] == a[i]);
        p[i] = j;
    }
// 递归求最小的j（j>0)， 求最小的前缀长度
// next[i],next[next[i]]next[next[next[i]]]......都是这个前缀串i的公共前后缀，而且只有它们是公共前后缀
    for(int i = 1; i <= n; i ++) {
        j = i;
        while(p[j]) j = p[j];  
        if(p[i] != 0) p[i] = j; // 记忆化，类比路径压缩
        ans += i - j;
    }
    cout <<ans <<endl;
    return 0;
}

• 统计每个前缀的出现次数

  • 在一个相同的字符串中统计其每个前缀出现次数
  • 在代码中我们首先统计每个前缀函数值在数组 fail 中出现了多少次，然后再计算最后答案：如果我们知道长度为 i 的前缀出现了恰好 ans[1] 次，那么该值必须被叠加至其最长的既是后缀也是前缀的子串的出现次数中。在最后，为了统计原始的前缀，我们对每个结果加 1。
  • 此外，倘若要计算 S 的前缀在 T 中出现的次数， 可以构造字符串 S + '#' + T, 利用前缀函数和类似的技巧，求出[|S| + 2, |S| + |T| + 1]的答案即可

using namespace std;
const int N = 1e6 + 50;
char a[N];
int fail[N];
int main()
{
    cin >>(a + 1);
    int n = strlen(a + 1);
    int j = 0; fail[1] = 0;
    for(int i = 2; i <= n; i ++) {
        while(j > 0 && a[j + 1] != a[i]) j = fail[j];
        if(a[j + 1] == a[i]) j ++;
        fail[i] = j;
    }
    vector<int> ans(n + 1);
    for(int i = 1; i <= n; i ++) ans[fail[i]]++;
    for(int i = n; i > 1; i --) ans[fail[i]] += ans[i];
    for(int i = 1; i <= n; i ++) ans[i]++;
    for(int i = 1; i <= n; i ++) cout <<ans[i] <<" ";
    return 0;
}

• 一个字符串中本质不同子串的数目

• 扩展 KMP（Z 函数） (luogu P5410)

  • 先理解z数组的含义， z数组表示即从 i 开始的后缀与 s 的最长公共前缀的长度 (LCP)。(从 i 开始的后缀表示从 i 向右拓展得到的子串， 如 bcd 是 abcdefg 从 1 开始的后缀， 又如 abacaba, z[3] = 1, z[5] = 3)
  • z数组的求法？？？

using namespace std;
const int N = 2 * 1e7 + 50, Inf = 0x3f3f3f3f;
i64 p[N], z[N];
void Z(char *s, int n)
{
    for(int i = 1; i <= n; i ++) z[i] = 0;
    z[1] = n;
    for(int i = 2, l = 0, r = 0; i <= n; i ++) {
        if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
        while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) z[i] ++;
        if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return;
}
void exkmp(char *s, int n, char *t, int m)
{
    Z(t, m);
    for(int i = 1; i <= n; i++) p[i] = 0;
    for(int i = 1, l = 0, r = 0; i <= n; i++) {
        if (i <= r) p[i] = min(z[i-l+1], r - i + 1);
        while (i + p[i] <= n && s[i + p[i]] == t[p[i] + 1]) p[i] ++;
        if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
}
char s[N], t[N];
int main()
{
    cin >>(s + 1) >>(t + 1);
    i64 n = strlen(s + 1), m = strlen(t + 1);
    exkmp(s, n, t, m);
    LL ans = 0;
    for(int i = 1; i <= m; i ++) ans ^= 1ll * i * (z[i] + 1);
    print(ans); putchar('\n'); ans = 0;
    for(int i = 1; i <= n; i ++) ans ^= 1ll * i * (p[i] + 1);
    print(ans); return 0;
}

• 失配树 (模板题)

  • 似于 KMP+LCA的结合, 利用 nest(前缀函数)的(不知名)性质 :
  • 这种性质类似于树上的父子关系，fa[i] , fa[fa[i]] , fa[fa[fa[i]]]....故而可以将其转化为一棵树(不用真正建树)。
  • 为了加快查询(遍历)速度, 采取类似于LCA的倍增策略, 即失配树。

using namespace std;
const int N = 1e6 + 50;
char s[N];
int n, fa[N][23], dep[N], m;
void KMP()
{
    int j = 0; dep[0] = 0; dep[1] = 1;
    for(int i = 2; i <= n; i ++) {
        while(j > 0 && s[j + 1] != s[i]) j = fa[j][0];
        j += (s[j + 1] == s[i]);
        fa[i][0] = j;
        dep[i] = dep[j] + 1; fa[i][0] = j;
    }
    for(int k = 1; k <= 21; k ++) 
        for(int i = 1; i <= n; i ++) 
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
    return;
}
int LCA(int x, int y) // 用tarjan 和 树链剖分更快
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 21; i >= 0; i --) 
        if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    // if(x == y) return x; 此处不能直接返回 ???
    for(int i = 21; i >= 0; i --) 
        if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
} 
int main()
{
    ios_base::sync_with_stdio,cin.tie(0),cout.tie(0);
    cin >>(s + 1); n = strlen(s + 1);
    KMP();
    cin >>m;
    for(int i = 1, x, y; i <= m; i ++) {
        cin >>x >>y;
        cout <<LCA(x, y) <<endl;
    }
    return 0;
}

• 例题详解

• Power Strings

• 推论 ：设字符串的长度为 len， 对于 任意 i \in [1, len]， 若 i \text{mod} (i - next_i) = 0 && next_i > 0， 则前 i 个字符循环， 循环节的长度为 \dfrac{i}{i - next_i}

• 证明 :

using namespace std;
const int N = 2 * 1e6 + 50;
char ch[N];
int fail[N];
int main()
{
    while(cin >>(ch + 1)) {
        memset(fail, 0, sizeof(fail));
        int n = strlen(ch + 1);
        if(ch[1] == '.' && n == 1) break;
        int j = 0;
        for(int i = 2; i <= n; i ++) {
            while(j > 0 && ch[j + 1] != ch[i]) j = fail[j];
            if(ch[j + 1] == ch[i]) j ++;
            fail[i] = j;
        } 
        if(fail[n] != 0 && n % (n - fail[n]) == 0) {
            cout <<(n / (n - fail[n])) <<endl;
        }
        else cout <<"1" <<endl;
    } 
    return 0;
}