字符串相关

坑什么的随便就挖好了。


Trie - 字典树

概述

也叫前缀树,用来保存字符串集合。从根到每一个单词结点的路径就是一个单词。
模板见ACAM.
Trie还可以改进,可以将后缀相同的单词收束,学有余力来过来看。

例1 [LA3942] Remember the Word

[Description]
给定最多4000个长度不超过100的单词,将一个长度不超过300000的字符串拆解成单词有多少成拆发。
[Solution]
DP+Trie.先预处理哪些区间[i,j]是单词(枚举+判断需$O(n^{2})$,我们可以直接从Trie下手),再线性转移。

例2 [UVa11732] “strcmp()”Anyone?

[Description] 给定不超过4000个长度不超过1000的字符串,求他们两两公共前缀总和。
[Solution] 在Trie上操作。


MP - 最小表示法

概述

大半年前看过一遍然后完全不记得了啊,再看的时候傻逼得吓人qwq
字符串什么的就是容易忘…
一种判循环同构的工具。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int maxn=1000;
char s[maxn];
void MP(){
int l=0,r=1,k=0,t;
while(l<n && r<n){
k=0;
while(s[l+k]==s[r+k]) k++;
if(s[l+k]<s[r+k]) r=r+k+1;
else l=l+k+1;
if(l==r) r++;
if(max(l,r)>=n) t=min(l,r);
}
for(int i=t;i<t+n;i++) putchar(s[i]);
}

KMP - 看*片

详述

请移步 >> http://codeplay0314.gitcafe.io/2015/04/19/KMP/

例1 [LA3026] Period

[Description]
求长度不超过$10^{6}$的字符串每个前缀的最长循环节,若不存在则不输出。
[Hint]
如串”aabaabaabaab”,ans[2]=1,ans[6]=2,ans[9]=3,ans[12]=4
[Solution]
非常有趣的题目,性质题。
计算字符串的next数组,若next[i]!=0 && i%(i-next[i])==0,则有s[next[i]+1]~s[i]为循环节,进而算出循环次数。


EXKMP - 扩展看*片

就是比KMP的同时求一个extend数组咯。

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn=100;
int next[maxn],extend[maxn];
char s[maxn],len1,t[maxn],len2;
void EXKMP(){
for(int i=0,j=-1,a,p;i<len1;i++){
if(j<0 || i+next[i-a]>=p){
if(j<0) j=0,p=i;
while(s[p]==t[j] && p<len1 && j<len2) p++,j++;
extend[i]=j,a=i;
}
else extend[i]=next[i-a];
}
}


Manacher - 马拉车

选了一篇讲得比较清晰的 >> http://blog.csdn.net/xingyeyongheng/article/details/9310555
需要注意的是文中为当前匹配搭配i+k,i为能匹配到最远的中心位置。
还有就是s[0]初始化成未知字符防止while的的时候越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
  scanf("%s",s+1);
int n=strlen(s+1),ans=0;
s[0]='*',s[2*n+1]='#';
for(int i=n;i;i--) s[2*i]=s[i],s[2*i-1]='#';
for(int i=1,id=0;i<=2*n+1;i++){
if(id+p[id]>i) p[i]=min(p[2*id-i],p[id]+id-i);
else p[i]=1;
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(id+p[id]<i+p[i]) id=i;
ans=max(ans,p[i]-1);
}
printf("%d\n",ans);
}

ACAM - AC自动机

$ACAM=Trie+KMP$
ACAM用于多个子串和母串的匹配,可以想到,KMP是线性结构上的字符串匹配,而AC自动机是在Trie上的匹配,详情见代码(过HDU2222测试)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct ACAM{
int val;
ACAM*nxt[26],*fail;
ACAM(){ val=0; fail=NULL; for(int i=0;i<26;i++) nxt[i]=NULL; }
void init(){ //初始化
if(!this) return;
for(int i=0;i<26;i++) if(nxt[i]){
this->nxt[i]->init();
delete nxt[i];
nxt[i]=NULL;
}
}
void insert(char*s){ //插入子串,操作同Trie
ACAM*u=this;
int len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
if(!u->nxt[v])
u->nxt[v]=new ACAM;
u=u->nxt[v];
}
u->val++;
}
void getFail(){ //计算每个结点的适配结点Fail
queue<ACAM*> q;
this->fail=this;
for(int i=0;i<26;i++) if(this->nxt[i]){
q.push(this->nxt[i]);
this->nxt[i]->fail=this;
}
while(!q.empty()){
ACAM*r=q.front(); q.pop();
for(int i=0;i<26;i++){
ACAM*&u=r->nxt[i],*v=r->fail;
if(!u) continue;
else q.push(u);
while(v!=this && !v->nxt[i]) v=v->fail;
u->fail=v->nxt[i]?v->nxt[i]:this;
}
}
}
int find(char*s){ //匹配
int ans=0;
ACAM*k=this;
int len=strlen(s);
for(int i=0;i<len;i++){
int c=s[i]-'a';
while(k!=this && !k->nxt[c]) k=k->fail;
k=k->nxt[c]?k->nxt[c]:this;
ACAM*k1=k;
while(k1!=this && k1->val>0){
ans+=k1->val;
k1->val=-1;
k1=k1->fail;
}
}
return ans;
}
};


SA- 后缀数组

lz写了一个小时忘记保存,一瞬间差点跳出窗外。呵呵。不管了。
直接丢代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct SA{
static const int maxn=10000+10;
int s[maxn];
int sa[maxn],height[maxn],n;
SA(){
scanf("%s",s);
n=strlen(s);
}
void getSA(){
int x[maxn],y[maxn],c[maxn];
for(int i=0;i<n;i++) c[x[i]=s[i]]++;
for(int i=1;i<=2;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1,m=2,p=0;k<=n && p<n;k<<=1,m=p){
p=0;
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
p=1,y[sa[0]]=0;
for(int i=1;i<n;i++) y[sa[i]]=x[sa[i-1]]==x[sa[i]] && x[sa[i-1]+k]==x[sa[i]+k]?p-1:p++;
swap(x,y);
}
}
void getHeight(){
int rank[maxn];
for(int i=0;i<n;i++) rank[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(k) k--;
int j=sa[rank[i]-1];
while(s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
}sa;

SAM - 后缀自动机


PAM - 回文自动机