最基础部分
定义
字符集,字符串(这东西显然不需要打一遍定义)
子串,这个东西表示一段连续的S[i...j],i≤j
有时候,用S[i...j],i>j表示空串
子序列,s[p1...pk],pi递增并且满足1≤p1<pk≤∣S∣
前缀,从串首开始到某个位置的子串。
后缀,从某个位置到串末尾的子串。为啥每次都会打成猴嘴
字典序,顾名思义就是按照字符顺序比较的方法,或者说以第i个字符为第i关键字进行大小比较,空集是最小的
回文串,倒着和正着都一样的串
输入,输出
哈希
把一个子串映射成为一个数字,一般的写法是这样的
f(S)=∑sip∣S∣−i
我们先令 n=∣S∣ 那
f(S)=s1∗pn−1+s2∗pn−2+...+sn
单独这样取模最后的结果太大了,我们还得模一个数,最好是质数,因为这样每个结果出现的概率相等(证明很容易,因此不放)。
代码写出来就是这样的
1
| for(i=1;i<=n;i++) f[i]=(f[i-1]*p+s[i]-'a')%modp;
|
然而现在我们只有 [1..i] 的哈希值,我们想要 [l,r] 的哈希值,那怎么办呢?
首先我们找到 l−1 的表达
f(S[1..(l−1)])=s1×pl−2+s2×pl−3+...+sl−1
然后 r 的表达
f(S[1..(r)])=s1 timespr−1+s2×pr−2+...+sr
观察第一项次数之差 r−1−(l−2)=r+l+1
那么我们给 l−1的表达乘 p 的这么多次方即可
f(S[1..(r)])−pr+l−1×f(S[1..(l−1)])
即为所求(显然记过是要让你自己推以下的)
那么这东西有什么用呢?
如果两个字符串相等的话,那么他们的哈希值一定相等,但是并不能保证哈希值相等,这两个串相等,不过这种概率很小,而且不可避免,不过都写了哈希了基本都确定是在水分了,被卡一两个点也能接受。
哈希冲突的概率到底是多少?
我们取n个哈希,每次都会有 modp1 的概率炸掉,那么炸掉的总概率是 1−(1−modp1)n
但是这样算其实是有问题的,参考 生日悖论 也就是说冲突的概率大概是 O(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) {
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 (实际上这东西也被人称为 next 数组 )表示长度最大的前缀后缀长度使得前缀后缀相等,对于这个字符串,我们可以轻易地手推出πi
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
S |
a |
b |
c |
a |
b |
c |
d |
π |
0 |
0 |
0 |
1 |
2 |
3 |
0 |
这东西有什么用呢?我们先不考虑,来看看怎么求到这个数组
首先一个显然的办法是对每个位置暴力枚举前缀后缀,然后暴力比较,时间复杂度为O(n3),优化可以用哈希,但是也应该注意到每次πi≤πi−1+1那么我们不用每一次都来重新枚举下标,实际上这个移动的上界也是很显然可以确定是O(N)级别了,似乎我们已经优化成了O(N)不过我们使用了哈希,我们继续推一下它的性质。
我们发现,因为最长移动距离是 1 时,这时候必然有Sπ[i]+1=s[i+1] 这时候π[i+1]=π[i]+1,否则我们就在找到下一个更短的 πj来贪心地匹配,想一下我们刚才得到的结论,发现预处理这个数组时间复杂度变成了O(N)
,然后这样一来,我们之后匹配一个字符串来,有了πi我们就可以保证当前匹配出的长度只增不减,同时我们在原来的模式串跳,最坏的复杂度为依然为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]]=i和sa[rk[i]]=i 不断推导求得后缀排名,每次双关键字化成了一个关键字,等价于倍增
SAM
后缀平衡树?