坑什么的随便就挖好了。

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]

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 - 看*片

详述

请移步 >> KMP算法 | Knuth–Morris–Pratt algorithm

例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数组咯。

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的的时候越界。

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测试）。

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写了一个小时忘记保存，一瞬间差点跳出窗外。呵呵。不管了。
直接丢代码。

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;

算法 | 字符串相关