字符串

Part 0:前言

**NK

Part 1：字符串的存储和基本操作

char、string 都行。

主要使用 char，但 string 拥有强大的 STL，这里举几个例子。

s.length() / s.size()：长度/大小
s.find(char c[],int begin=0)：从位置 $begin$ （不写默认为 $0$ ）开始查找字符（串） $c$ 并返回第一个出现的位置。没找到时返回 s.npos。
s.erase(pos,n)：删除从pos开始的n个字符。
s.erase(pos)：删除pos处的一个字符。（pos是string类型的迭代器，也就是 pos=s.begin()+位置）

Part 2：KMP算法

luogu P3375 【模板】KMP

求模式串在主串中的出现情况。

如果直接暴力匹配字符串肯定是不行的。

但是如果对于每次失配之后，不从头重新开始枚举，而是根据已经得知的数据，从某个特定的位置开始匹配，就可以啦。

所以我们定义 $kmp_i$ 为匹配到模式串的第 $i$ 位，失配时跳到哪一位。（其中 $kmp_0=kmp_1=1$ ，因为此时只能跳到第一位了awa）

所以匹配就很简单了：

t=0;
for(int i=1;a[i];i++){
	while(t&&b[t+1]!=a[i])t=kmp[t];//若失配则跳到上一个位置
	if(b[t+1]==a[i])t++;//匹配成功
	if(t==strlen(b+1)){//匹配完成
		printf("%d\n",i-strlen(b+1)+1);
		t=kmp[t];
	}
}

但是我们要怎么求这个 $kmp$ 呢？

可以考虑自己匹配自己。（也就是先和自己跑一遍匹配）

t=0;
for(int i=2;b[i];i++){
	while(t&&b[i]!=b[t+1])t=kmp[t];
	if(b[t+1]==b[i])t++;
	kmp[i]=t;
}

然后...就没了qAq。

Part 3：字典树

luogu P8306 【模板】字典树

快，省空间。

字典树就是将大量字符串转化为树形结构。

定义 $t_{i,j}$ 表示当前节点 $i$ 的字符为 $j$ 。

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

Part 3.1：插入操作

void add(char s[]){
	int p=0;
	for(int i=0;s[i];i++){
		int v=getnum(s[i]);//为s[i]的值
		if(!t[p][v])t[p][v]=++id;//id为节点编号
		p=t[p][v];//迭代
		cnt[p]++;
	}
}

Part 3.2：查询操作

int find(char s[]){
	int p=0;
	for(int i=0;s[i];i++){
		int v=getnum(s[i]);
		if(!t[p][v])return 0;//没查到
		p=t[p][v];
	}
	return cnt[p];
}

Part 4：AC自动机

在字典树上跑KMP。

在KMP中我们用 $kmp_i$ 表示失配后跳到哪一位。

那我们为什么不在字典树上构建一个类似的数组以解决多模式串匹配呢呢？

直接上代码：

插入（和字典树一样awa）：

void add(char *s){
	int u=0;
	for(int i=0;s[i];i++){
		int v=s[i]-'a';
		if(!t[u][v])t[u][v]=++cnt;
		u=t[u][v];
	}
	val[u]++;//统计数量
}

构建 fail 数组：

void build(){
	queue<int> q;//因为要先处理出父亲节点的fail，所以用bfs
	for(int i=0;i<26;i++)
		if(t[0][i])fail[t[0][i]]=0,q.push(t[0][i]);//与根节点相连的统一指向根节点
	while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        if(t[u][i])fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);//若有，fail则为其父亲节点失配后下一个为i的点
        else t[u][i]=t[fail[u]][i];//不然，将其相连
    }
}

匹配：

int query(char *s){
    int len=strlen(s);
	int u=0,ans=0;
    for(int i=0;i<len;i++){
        u=t[u][s[i]-'a'];//跳
        for(int t=u;t&&~val[t];t=fail[t])ans+=val[t],val[t]=-1;
      //当此节点存在同时其cnt未被遍历
      //将答案加上所搜索的字符串中所包含的该单词数
      //标记
    }
    return ans;
}

Part 5：后缀数组

首先，求后缀的排名 $rank_i$ & 这个后缀是第几名 $sa_i$ 。

$rank_i$ 表示第 $i$ 个后缀的排名。
$sa_i$ 表示第 $i$ 名是哪个后缀。

所以该怎么做呢？

Part 5.1：暴力快排

暴力存储所有后缀再排序，时间复杂度 $O(n^2logn)$ 。

（其中快排 $O(nlogn)$ ，字符串比较 $O(n)$ ）

Part 5.2：倍增+快排

不说了， $O(nlog2n)$ 。

Part 5.3：倍增+基数排序

主要讲这个 $O(nlogn)？$ 的算法。

倍增，每次通过两个关键字进行基数排序。

最后统计排名，并考虑并列的情况。

当排出 $n$ 名了后退出即可。

luogu P3809 【模板】后缀排序

Part 5.4：求height

证明：h[i]>=h[i-1]-1

~~大佬的证明：~~

首先我们不妨设第i-1个字符串按排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。

这时，依据height[]的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rk[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。

第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rk[i-1]]就是0了呀，那么无论height[rk[i]]是多少都会有height[rk[i]]>=height[rk[i-1]]-1，也就是h[i]>=h[i-1]-1。

第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rk[i-1]]，

那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rk[i-1]]-1。

到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。但是我们前面求得，有一个排在i前面的字符串k+1，LCP(rk[i],rk[k+1])=height[rk[i-1]]-1;

又因为height[rk[i]]=LCP(i,i-1)>=LCP(i,k+1)

所以height[rk[i]]>=height[rk[i-1]]-1，也即h[i]>=h[i-1]-1。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int k=1,n,st[256],rank0[N<<1],cnt[N],tmp[N],sa[N],rank1[N],height[N];
char str1[N];
int main(){
	scanf("%s",str1+1);
	n=strlen(str1+1);
	for(int i=1;i<=n;i++)st[str1[i]]=1;//浅浅排一下第一个字符
	for(int i=1;i<=255;i++)st[i]+=st[i-1];
	for(int i=1;i<=n;i++)rank0[i]=st[str1[i]];
	for(int p=1;k!=n;p=p*2){//倍增直到所有后缀都排出名来
		memset(cnt,0,sizeof cnt);//按第二关键字排序
		for(int i=1;i<=n;i++)cnt[rank0[i+p]]++;
		for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];//前缀和
		for(int i=n;i>=1;i--)tmp[cnt[rank0[i+p]]--]=i;//第二关键字排序结果
		memset(cnt,0,sizeof cnt);//按第一关键字排序
		for(int i=1;i<=n;i++)cnt[rank0[i]]++;
		for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];//前缀和
		for(int i=n;i>=1;i--)sa[cnt[rank0[tmp[i]]]--]=tmp[i];//第一关键字排序结果，也就是最终排序的结果sa[i]
		k=1;
		rank0[sa[1]]=k;//排名，第一个肯定为1
		memcpy(rank1,rank0,sizeof(rank1));
		for(int i=2;i<=n;i++){
			if(!(rank1[sa[i]]==rank1[sa[i-1]]&&rank1[sa[i]+p]==rank1[sa[i-1]+p]))k++;//检测两个关键字是否相同，若相同则排名相同
			rank0[sa[i]]=k;
		}
	}
  	k=0;//开始求height
	for(int i=1;i<=n;i++){
		if(rank0[i]==1)continue;//第一名height为0
		if(k)k--;//h[i]>=h[i-1]-1;
		while(str1[i+k]==str1[sa[rank0[i]-1]+k])k++;
		height[rank0[i]]=k;
	}
	for(int i=1;i<=n;i++)
		printf("%d%c",sa[i],(i==n)?'\n':' ');
	return 0;
}

Part 6：后缀自动机

自己学去，劳资不会。

字符串算法总结

字符串