最基础部分

定义

字符集,字符串(这东西显然不需要打一遍定义)

子串,这个东西表示一段连续的S[i...j],ijS[i...j],i\leq j

有时候,用S[i...j],i>jS[i...j],i>j表示空串

子序列,s[p1...pk],pis[p_1...p_k],p_i递增并且满足1p1<pkS1\leq p_1<p_k\leq|S|

前缀,从串首开始到某个位置的子串。

后缀,从某个位置到串末尾的子串。为啥每次都会打成猴嘴

字典序,顾名思义就是按照字符顺序比较的方法,或者说以第ii个字符为第ii关键字进行大小比较,空集是最小的

回文串,倒着和正着都一样的串

输入,输出

哈希

把一个子串映射成为一个数字,一般的写法是这样的

f(S)=sipSif(S)=\sum s_ip^{|S|-i}

我们先令 n=Sn=|S|

f(S)=s1pn1+s2pn2+...+snf(S)=s_1*p^{n-1}+s_2*p^{n-2}+...+s_n

单独这样取模最后的结果太大了,我们还得模一个数,最好是质数,因为这样每个结果出现的概率相等(证明很容易,因此不放)。

代码写出来就是这样的

1
for(i=1;i<=n;i++) f[i]=(f[i-1]*p+s[i]-'a')%modp;

然而现在我们只有 [1..i][1..i] 的哈希值,我们想要 [l,r][l,r] 的哈希值,那怎么办呢?

首先我们找到 l1l-1 的表达

f(S[1..(l1)])=s1×pl2+s2×pl3+...+sl1f(S[1..(l-1)])=s_1 \times p^{l-2}+s_2 \times p^{l-3}+...+s_{l-1}

然后 rr 的表达

f(S[1..(r)])=s1 timespr1+s2×pr2+...+srf(S[1..(r)])=s_1\ times p^{r-1}+s_2 \times p^{r-2}+...+s_{r}

观察第一项次数之差 r1(l2)=r+l+1r-1-(l-2)= r+l+1

那么我们给 l1l-1的表达乘 pp 的这么多次方即可

f(S[1..(r)])pr+l1×f(S[1..(l1)])f(S[1..(r)])-p^{r+l-1}\times f(S[1..(l-1)])

即为所求(显然记过是要让你自己推以下的)

那么这东西有什么用呢?

如果两个字符串相等的话,那么他们的哈希值一定相等,但是并不能保证哈希值相等,这两个串相等,不过这种概率很小,而且不可避免,不过都写了哈希了基本都确定是在水分了,被卡一两个点也能接受。

哈希冲突的概率到底是多少?

我们取nn个哈希,每次都会有 1modp\frac{1}{modp} 的概率炸掉,那么炸掉的总概率是 1(11modp)n1-(1-\frac{1}{modp})^n

但是这样算其实是有问题的,参考 生日悖论 也就是说冲突的概率大概是 O(modp)O(\sqrt{modp}) 级别的,那怎么办呢?双哈希即可

Trie

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
#include<bits/stdc++.h>

using namespace std;

const int maxn=10086;

char a[120];

int t[maxn*26][26];
int eof[maxn*26],T,tot=1;

void ins_trie_tree(int x,int len,int mxlen)
{
// cout<<a[len]<<endl;
if(len==mxlen+1)
{
eof[x]++;
return ;
}
if(t[x][a[len]-'a']) ins_trie_tree(t[x][a[len]-'a'],len+1,mxlen);
else t[x][a[len]-'a']=++tot,ins_trie_tree(tot,len+1,mxlen);
}

char tmp[120];

void coutree(int x,int dep)
{
for(int i=1;i<=eof[x];i++)
{
printf("%s\n",&tmp[1]);
}
for(int i=0;i<=25;i++)
{
if(t[x][i])
{
tmp[dep+1]='a'+i;
coutree(t[x][i],dep+1);
tmp[dep+1]=0;
}
}
}

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",a+1);
ins_trie_tree(1,1,strlen(a+1));
}
coutree(1,0);
}

低科技

KMP

这东西打这个发现是真的没懂,于是重新去学了一遍

我们考虑一般的字符串匹配问题,如果我们用哈希的话,运气好出题人是卡不掉的,但是出题人卡不卡的掉你全靠运气,所以有更保险的写法还是写更保险的吧(除非写不出来了)

我们定义 πi\pi_i (实际上这东西也被人称为 nextnext 数组 )表示长度最大的前缀后缀长度使得前缀后缀相等,对于这个字符串,我们可以轻易地手推出πi\pi_i

下标 1 2 3 4 5 6 7
SS a b c a b​ c​ d​
π\pi 00 00 00 11 22 33 00

这东西有什么用呢?我们先不考虑,来看看怎么求到这个数组

首先一个显然的办法是对每个位置暴力枚举前缀后缀,然后暴力比较,时间复杂度为O(n3)O(n^3),优化可以用哈希,但是也应该注意到每次πiπi1+1\pi_i \leq \pi_{i-1}+1那么我们不用每一次都来重新枚举下标,实际上这个移动的上界也是很显然可以确定是O(N)O(N)级别了,似乎我们已经优化成了O(N)O(N)不过我们使用了哈希,我们继续推一下它的性质。

我们发现,因为最长移动距离是 11 时,这时候必然有Sπ[i]+1=s[i+1]S_{\pi[i]+1}=s[i+1] 这时候π[i+1]=π[i]+1\pi [i+1]=\pi[i]+1,否则我们就在找到下一个更短的 πj\pi_j来贪心地匹配,想一下我们刚才得到的结论,发现预处理这个数组时间复杂度变成了O(N)O(N)

,然后这样一来,我们之后匹配一个字符串来,有了πi\pi_i我们就可以保证当前匹配出的长度只增不减,同时我们在原来的模式串跳,最坏的复杂度为依然为O(N)O(N)

补一个代码

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e6+10;

char ms[maxn],ts[maxn];
int pi[maxn];
int n,m;

int main()
{
ios::sync_with_stdio(false);
register int i,j;
scanf("%s %s",ts+1,ms+1);
j=0;
n=strlen(ms+1);
for(i=2;i<=n;i++)
{
while(j&&ms[j+1]!=ms[i]) j=pi[j];
if(ms[j+1]==ms[i]) j++;pi[i]=j;
}
m=strlen(ts+1);
j=0;
for(i=1;i<=m;i++)
{
while(j&&ms[j+1]!=ts[i]) j=pi[j];
if(ms[j+1]==ts[i]) j++;
if(j==n) cout<<i-n+1<<endl,j=pi[j];
}
for(i=1;i<=n;i++) cout<<pi[i]<<" ";
return 0;
}

AC自动机

马拉车

高科技

扩展KMP

SA

本质上是根据rk[sa[i]]=irk[sa[i]]=isa[rk[i]]=isa[rk[i]]=i 不断推导求得后缀排名,每次双关键字化成了一个关键字,等价于倍增

SAM

后缀平衡树?