字符串

hash

这里展示使用自然溢出的hash

cpp
1
2
3
4
5
6
7
8
9
ull hashs[_],bases[_],base=131311;

bases[0]=1;
for(int i=1;i<=n;i++){
	bases[i]=bases[i-1]*base;
	hashs[i]=hashs[i-1]*base+str[i];
}

inline ull range(int l,int r){return hashs[r]-hashs[l-1]*bases[r-l+1];}

求最小循环节

首先线性筛预处理出素数 我们有下面两个性质

• 若长度为 $n$ 的前缀是 str 的循环节，则 $k*n$ 也是 str 的循环节 （ $n$ 和 $k*n$ 都是字符串长度的因数）

• 若字符串从 1 到 (len-n) 的子字符串与从 (n+1) 到 len 的子字符串是相同的，且 n 为 len 的因数，则长度为 n 的前缀是该字符串的循环节

于是对于求给定区间的最小循环节，我们可以这样处理

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
	while(q--){
		int l,r;cin>>l>>r;
		int len=r-l+1,cnt=0;
		while(len>1){//这一步是分解质因数
			num[++cnt]=nxt[len];
			len/=nxt[len];
		}
		len=r-l+1;
		for(int i=1;i<=cnt;i++){//根据上述第一个性质，我们尝试把一个质因子除掉后还是不是循环节
			int tmp=len/num[i];
			if(range(l,r-tmp)==range(l+tmp,r)) len=tmp;//根据上述第二个性质判断
		}
		cout<<len<<endl;;
	}

求最长公共前缀

【模板】后缀排序

读入一个长度为 $n$ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $1$ 到 $n$。

直接使用sort对每个字符串进行排序的时间复杂度其实是大于 $O(n^2)$ 的，因为两个字符串之间的比较的复杂度是 $O(n)$ 的。为了快速比较两个字符串的字典序，我们考虑求出两个字符串的LCP，然后看LCP下一个字符哪个字符串的大

使用hash+二分来求

cpp
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
#include<bits/stdc++.h>
#define _ 1000006
#define ull unsigned long long
using namespace std;

ull base=131311,hashs[_],bases[_];
inline ull range(int l,int r){return l<=r? hashs[r]-hashs[l-1]*bases[r-l+1]:0;}
char str[_];
int n,a[_];

inline bool cmp(int x,int y){
	int l=0,r=min(n-x+1,n-y+1),ans=0;//r处的意思是取两个字符串之间的长度最小的那个字符串的长度
	while(l<=r){
		int mid=(l+r)>>1;
		if(range(x,x+mid-1)==range(y,y+mid-1)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(ans==min(n-x+1,n-y+1)) return x>y;
	else return str[x+ans]<str[y+ans];
}

int main(){
	cin>>str+1;
	n=strlen(str+1);
	bases[0]=1;
	for(int i=1;i<=n;i++){
		bases[i]=bases[i-1]*base;
		hashs[i]=hashs[i-1]*base+str[i];
		a[i]=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
	return 0;
}

KMP

处理nxt数组

cpp
1
2
3
4
5
6
7
int p=0;
nxt[1]=0;
for(int i=1;i<m;i++){
	while(p>0&&b[i+1]!=b[p+1]) p=nxt[p];
	if(b[i+1]==b[p+1]) p++;
	nxt[i+1]=p;
}

$nxt[i]$ 表示一直到位置i（包括i）的前缀字符串的最长公共前后缀长度
并且，如果 $n \bmod (n-nxt[n])=0$ 则该字符串是由前缀长度 $n-nxt[n]$ 的子串进行若干次拼接得到的

匹配

cpp
1
2
3
4
5
6
p=0;
for(int i=0;i<n;i++){
	while(p>0&&b[p+1]!=s[i+1]) p=nxt[p];
	if(b[p+1]==s[i+1]) p++;
	if(p==m) ans++;
}

trie树

普通trie树

cpp
1
2
3
4
5
6
7
8
9
10
struct Node{int w,son[62];} trie[3000006];
int size;
inline void put(string str){
	int p=0;
	for(int i=0,now;i<str.size();i++){
		if(!trie[p].son[now=str[i]-'a']) trie[p].son[now]=++size;
		p=trie[p].son[now];
		trie[p].w++;
	}
}

01trie作平衡树

$w[]$ 用来kth，rak操作。$num[]$ 用来存放当前节点表示的数，省去了位运算的过程

有可能读入负数，需要先加上一个偏移量变成正数

加入操作

cpp
1
2
3
4
5
6
7
8
9
10
11
12
const int off=10000000;
int trie[10000007][2],num[10000007],w[10000007],size=1;
inline void add(int x,int c){
	int p=1;
	x+=off;
	for(int i=32,now;i>=0;i--){
		if(!trie[p][(now=((x>>i)&1))]) trie[p][now]=++size;
		p=trie[p][now];
		w[p]+=c;
	}
	num[p]=x;
}

rak操作。这个操作返回的是比给定的数小的个数。求排名还需要加一

cpp
1
2
3
4
5
6
7
8
9
inline int rak(int x){
	int p=1,res=0;
	x+=off;
	for(int i=32,now;i>=0;i--){
		if(now=((x>>i)&1)) res+=w[trie[p][0]];
		p=trie[p][now];
	}
	return res;
}

kth操作

cpp
1
2
3
4
5
6
7
8
inline int kth(int k){
	int p=1;
	for(int i=32,now;i>=0;i--){
		if(w[trie[p][0]]<k) k-=w[trie[p][0]],p=trie[p][1];
		else p=trie[p][0];
	}
	return num[p]-off;
}

插入 add(x,1);

删除 add(x,-1);

求排名 cout<<rak(x)+1<<endl;

求第x小 cout<<kth(x)<<endl;

求前驱 cout<<kth(rak(x))<<endl;

求后继 cout<<kth(rak(x+1)+1)<<endl;

Manacher

对字符串处理

cpp
1
2
3
4
5
6
	str[0]='~';
	str[1]='|';
	cnt=1;
	char c=getchar();
	while(c<'a'||c>'z') c=getchar();
	while(c>='a'&&c<='z') str[++cnt]=c,str[++cnt]='|',c=getchar();

求p数组

cpp
1
2
3
4
5
	for(int t=1,r=0,mid=0;t<=cnt;t++){
		if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
		while(str[t-p[t]]==str[t+p[t]]) ++p[t];
		if(p[t]+t>r) r=p[t]+t-1,mid=t;
	}

$p[t]-1$ 才是回文串长度