KMP与Trie

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;
}

注意p和idx初始值要相同，不然会出问题