KMP与Trie

Breeze-zyh / 2023-08-03 / 原文

KMP算法

KMP算法用于解决字串与母串的匹配问题，可看作哈希的简单写法，时间复杂度O(m+n)

KMP算法的核心优势在于相对于暴力枚举，它可以省去重复的步骤，从而将匹配过程由O(mn)优化为近似O(2m)，该算法的核心在于寻找子串前缀与后缀重合的最大长度，也就是next数组，那么怎么求呢？就是将子串自匹配

代码如下：

cin >> (a+1);
    l = strlen(a+1);
    for(int i = 2,j = 0;i <= l;i++){
        while(j && a[i] != a[j+1]) j = nxt[j];
        if(a[i] == a[j+1]) j++;
        nxt[i] = j;
    }

那么KMP算法的具体用法有哪些呢？大致分为三种

一、 求最小循环节

例如：我们在abababab中，找到其前后缀重复的最大长度，也就是next[8]，此时其值为6，不难发现s1-6 = s3-8，s1-2 = s7-8，由此可推出其最小循环节长度为二，也就是L-next[L];

二、 求一个字符串是由多少个相同字符串重复组成的

分为两种情况：可重复的：直接用总长度除以最小循环节

int k = l-nxt[l]; 
if(l%k) printf("1\n");
else printf("%d\n",l/k);

不可重复的：子母串正常匹配，然后匹配到答案++，j归零

for(int i = 1,j = 0;i <= lb;i++){
    while(j && b[i] != a[j+1]) j = nxt[j];
    if(b[i] == a[j+1]) j++;
    if(j == la) ans++,j = 0;
}
printf("%d\n",ans);

三、 题面如下

串是有限个小写字符的序列，特别的，一个空序列也可以是一个串。一个串 P 是串 A 的前缀，当且仅当存在串 B，使得 A=PB。如果P≠A并且 P 不是一个空串，那么我们说 P 是 A 的一个 proper 前缀。

定义 Q 是 A 的周期，当且仅当 Q 是 A 的一个 proper 前缀并且 A 是 QQ 的前缀（不一定要是 proper 前缀）。比如串 abab 和 ababab 都是串 abababa 的周期。串 A 的最大周期就是它最长的一个周期或者是一个空串（当 A 没有周期的时候），比如说，ababab 的最大周期是 abab。串 abc 的最大周期是空串。

给出一个串，求出它所有前缀的最大周期长度之和。

思路：求出最小next数组，用总长度减去即是答案

原因：next数组定义为前后缀重合最大长度，那么以这个长度切开再扩倍一定是可以前后相接的，代码：

#include<bits/stdc++.h>
using namespace std;
char a[1000005];
int n,la,lb,nxt[1000005];
long long ans;
int main(){
    scanf("%d",&n);
    cin >> (a+1);
    for(int i = 2,j = 0;i <= n;i++){
        while(j && a[i] != a[j+1]) j = nxt[j];
        if(a[i] == a[j+1]) j++;
        nxt[i] = j;
    }
    int q;
    for(int i = 1;i <= n;i++){
        q = i; 
        while(nxt[q]) q = nxt[q];
        if(nxt[i]) nxt[i] = q;
        ans+=i-q;
    }
    printf("%lld",ans);
    return 0;
}

Trie字典树

解决多串前缀匹配问题

核心：有点更新指针，继续走，无点建点，一个串走完需标记

模板

#include<bits/stdc++.h>
using namespace std;
int t,n,tree[100005][15],idx,mk[100005],q,l;
string a;
bool insert(string s){
    int c,p = 0,flag = 0;
    for(int i = 0;i < l;i++){
        c = s[i] - '0';
        if(!tree[p][c]){
            tree[p][c] = ++idx;
            p = tree[p][c];
        }else{
            p = tree[p][c];
            if(mk[p]||i == l-1) flag = 1;
        }
    }
    mk[idx]++;
    return flag;
}
int main(){
    scanf("%d",&t);
    for(int i = 1;i <= t;i++){
        scanf("%d",&n);
        q = 0;
        idx = 0;
        memset(tree,0,sizeof(tree));
        memset(mk,0,sizeof(mk));
        for(int j = 1;j <= n;j++){
            cin >> a;
            l = a.size();
            if(insert(a)){
                q = 1;
            }
        }
        if(!q) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}