字符串基础

字符串哈希


$hash$思想在字符串上的应用

$hash(i)=(hash(i-1)*B+s[i])$%$P$
$B$:进制数 参考:$457,251,2333,149,373$
$P$:模数 参考:$987654323,666666667,23456789$

姿势

双模、自然溢出
从$i$开始长为$len$子串的哈希值:$hash(i+len-1)-hash(i-1)*fac(len)$
$hash$+二分求$LCP$


KMP算法


在文本串$S$中匹配模板串$T$

next()函数

$next(i)$表示状态$i$失配后应转移到的状态
具体来说,$next(i)$表示前$i$位串的前缀和后缀的最长匹配(不包括$i$)
预处理$next()$相当于$T$自我匹配
性质:若$next(i)!=0$,且$i$%$(i-next(i))=0$,则字符串前$i$位循环,循环节长度为$i-next(i)$,循环次数为$i/(i-next(i))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getnext(){//start with 1
for(int i=2,j=0;i<=m;i++){
while(j&&p[i]!=p[j+1]) j=nex[j];
if(p[i]==p[j+1]) j++;
nex[i]=j;
}
}

void kmp(){
for(int i=1,j=0;i<=n;i++){
while(j&&s[i]!=p[j+1]) j=nex[j];
if(s[i]==p[j+1]) j++;
if(j==m) ans.push_back(i-m+1);
}
}


扩展KMP算法


对文本串$S=|n|$和模板串$T=|m|$
记$ext(i)$表示$Suffix(S,i)$与$T$的$LCP$长度
若$ext(i)=m$,说明找到了一个$T$,因此将其视为$KMP$问题的扩展

next()函数

辅助数组$next(i)$表示$Suffix(T,i)$与$T$的$LCP$长度
预处理方法类似$KMP$,相当于$T$与自己做$exKMP$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getnext(){//start with 1
int mx=mxp=0;
for(int i=2;i<=n;i++){
mxp=mxp>i?mxp:i;
nex[i]=min(mxp-i,nex[i+1-mx]);
while(T[nex[i]+1]==T[nex[i]+i]) nex[i]++;
if(i+nex[i]>mxp) mx=i;
mxp=mx+nex[mx];
}
}

void exkmp(){
int mx=mxp=0;
for(int i=1;i<=n;i++){
mxp=mxp>i?mxp:i;
ext[i]=min(mxp-i,nex[i+1-mx]);
while(T[ext[i]+1]==S[ext[i]+i]) ext[i]++;
if(i+ext[i]>mxp) mx=i;
mxp=mx+ext[mx];
}
}


Trie树


储存一个字符串集合

让$LCP$相同的字符串共用结点,并在叶子结点上附加信息

1
2
3
4
5
6
7
8
9
10
#define idx s[i]-'a'

void insert(int v=1){
int x=0,len=strlen(s);
for(int i=0;i<len;i++){
if(!c[x][idx]) c[x][idx]=++tot;
x=c[x][idx];
}
dang[x]=v;
}


AC自动机


在文本串$S$中匹配模板串集合$T={T_1,T_2,…,T_k}$

将模板串集合$T$建成一棵$Trie$树

转移函数

$trans(x,c)$为从状态$x$沿字符$c$的$Trie$边走到的点
$fail(x)$,失配函数,指向的点$y$满足:$str(y)$为$str(x)$的最长后缀

构造

按$bfs$序构造
假设已经得到了$fail(u)$,有$v=trans(u,c)$,现在求$fail(v)$
只需要从$u$的后缀中找到第一个有$c$的出边的点

1
2
3
4
5
6
7
8
9
void getfail(){  
l=0,q[r=1]=0,fail[0]=-1;
while(l!=r){
int x=q[++l];
for(int i=0;i<26;i++)
if(c[x][i]) q[++r]=c[x][i],fail[c[x][i]]=!x?0:c[fail[x]][i];
else c[x][i]=!x?0:c[fail[x]][i];
}
}


最小表示法


对于一个环状字符串,将其断开可以得到n个串,其中字典序最小的串称为最小表示

通过维护两个指针实现

1
2
3
4
5
6
7
8
9
10
11
12
int mr()
{
int i=0,j=1,k=0;
while(i<n&&j<n){
for(;k<n&&s[i+k]==s[j+k];k++);
if(k==n) return i;
if(s[i+k]>s[j+k]) i+=k+1;
else j+=k+1;
if(i==j) j++;
}
return min(i,j);
}
分享到: