字符串哈希
设一个字符串 \(s\),长度为 \(len\),定义一个大质数 \(base\),那么求哈希的式子为:
\[hash(s)=\sum^{len}_ {i=1} s_i \times base^{len-i} \]\(base\) 的次方可以由 \(power\) 数组初始化得到,那么如果把哈希当做一个 \(base\) 进制的数的话,不难想出用哈希数组 \(h\) 维护前缀和的方法求一个子串的哈希值,也就是:
\[hash(s[l:r])=h_r-h_{l-1}\times base^{r-l+1} \]kmp
解决在“文章” \(s1\) 中匹配单词 \(s2\) 的问题。
维护一个数组 \(nxt\) 表示在单词 \(s2\) 中最大真前后缀的长度,也就是对于字符串 \(s2=\text{abababaac}\) 中 \(nxt(7)=5\),因为 \(s2[1:5]=\text{ababa},s2[3:7]=\text{ababa}\),所以最大真前后缀就是 \(5\),那么当我们在更新 \(nxt\) 数组时,如果失配,也就是下一位不满足条件,该如何解决?
假设当前字符串处理到 \(i\) 位,目前最大真前后缀长为 \(j\),那么如果出现 \(s2[i] \neq s2[j+1]\) 的情况,就是失配,因为保证 \(s2[1:j]=s2[i-j+1:i]\),所以我们可以一直跳回 \(nxt[j]\) 的位置直到可以匹配,易得这样的复杂度是 \(O(n+m)\) 的。
同理,预处理之后,当匹配 \(s1\) 时,也可以按照同样的原理,用数组 \(f\) 记录能匹配的 \(s2\) 最长前缀,当最长前缀就是 \(s2\) 时,匹配成功。
代码
char s1[maxn],s2[maxn];
ll len1,len2;
ll nxt[maxn],f[maxn];
inline void get_nxt(){
nxt[1]=0;
for(int i=2,j=0;i<=len2;i++){
while(j&&s2[i]!=s2[j+1]){
j=nxt[j];
}
if(s2[i]==s2[j+1]) j++;
nxt[i]=j;
}
}
inline void kmp(){
for(int i=1,j=0;i<=len1;i++){
while(j==len2||(j&&s1[i]!=s2[j+1])){
j=nxt[j];
}
if(s1[i]==s2[j+1]) j++;
f[i]=j;
if(f[i]==len2){
printf("%d\n",i-len2+1);
}
}
}
例题
1.P3435 OKR-Periods of Words
可以发现,如果满足题目要求的条件的话,\(a[len(Q)+1:len(a)]\) 的部分也是 \(a\) 的一个 \(border\),那么只要 \(border\) 越小,结果就越大,所以对于每个前缀都跳 \(nxt()\) 直到为 \(0\)。
2.P4824 Censoring S
一个很精妙的操作是,不对字符串进行修改,当我们正常匹配 \(\operatorname{kmp}\) 的时候指针 \(j\) 是不断维护的,那么如果删去一个 \(T\) 后,把 \(j\) 改为删去后已经匹配了的长度就可以继续进行,那就需要一个栈维护下标,最后把没有弹出的全部输出。
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
ls=strlen(s+1),lt=strlen(t+1);
get_nxt();
for(int i=1,j=0;i<=ls;i++){
while(j&&s[i]!=t[j+1]) j=nxt[j];
if(s[i]==t[j+1]) j++;
f[i]=j;
stac[++top]=i;
if(f[i]==lt){
top-=lt;
j=f[stac[top]];
}
}
for(int i=1;i<=top;i++){
//printf("%d ",stac[i]);
printf("%c",s[stac[i]]);
}
return 0;
}
3.P2375 动物园
\(num(i)\) 的实际意义为在 \(s[1:i/2]\) 中,\(border\) 的个数,那么用 \(cnt(i)\) 统计,每次处理向前跳到前半区间即可。
inline void get_nxt(){
nxt[1]=0,cnt[1]=1;
for(int i=2,j=0;i<=len;i++){
while(j&&s[i]!=s[j+1]) j=nxt[j];
if(s[i]==s[j+1]) j++;
nxt[i]=j;
cnt[i]=cnt[j]+1;
}
}
inline void get_ans(){
for(int i=2,j=0;i<=len;i++){
while(j&&s[i]!=s[j+1]) j=nxt[j];
if(s[i]==s[j+1]) j++;
while((j<<1)>i) j=nxt[j];
ans=(ans*(ll)(cnt[j]+1))%mod;
}
}
4.P3193 HNOI2008 GT考试
若保证 \(X\) 中不包含 \(A\),就是保证 \(X\) 中对 \(A\) 的匹配是不完全的,那么我们设置 \(dp[i][j]\) 表示目前构建的长度为 \(i\) 的 \(X\) 后缀与 \(A\) 长度为 \(j\)的前缀匹配的情况数,可以得到最后的答案为:
\[ans=\sum_{i=0}^{m-1} dp[n][i] \]考虑转移,可以发现第 \(i\) 位的结果是由 \(i-1\) 位的结果和字符串的前缀增加一位后匹配后缀方案数得来的,而这个方案数设为 \(g[i][j]\),表示在现有的字符串后加一个字符,使得其 \(border\) 与 \(j\) 相等的方案数,转移方程为:
\[dp[i][j]=\sum_{k=0}^{m-1} dp[i-1][k]\times g[k][j] \]然后发现已知 \(A\) 所以 \(g\) 的整体是可以初始化出来的,那么就是矩阵乘法了,然后 \(dp \times g^n\) 后的 \(\sum_{i=0}^{m-1} dp[0][i]\) 就是答案。
int n,m,p;
char s[35];
int nxt[35];
struct mat{
int num[35][35];
mat(){
memset(num,0,sizeof(num));
}
}dp,g;
mat operator *(mat a,mat b){
mat ans;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
for(int k=0;k<m;k++){
ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%p)%p;
}
}
}
return ans;
}
mat q_pow(mat x,int k){
mat ans;
for(int i=0;i<m;i++){
ans.num[i][i]=1;
}
while(k){
if(k&1) ans=ans*x;
x=x*x;
k>>=1;
}
return ans;
}
inline void get_nxt(){
for(int i=2,j=0;i<=m;i++){
while(j&&s[j+1]!=s[i]){
j=nxt[j];
}
if(s[j+1]==s[i]) j++;
nxt[i]=j;
}
}
inline void kmp(){
for(int i=0;i<m;i++){
for(char ch='0';ch<='9';ch++){
int j=i;
while(j&&s[j+1]!=ch){
j=nxt[j];
}
if(s[j+1]==ch) j++;
g.num[i][j]=(g.num[i][j]+1)%p;
}
}
}
int ans=0;
int main(){
n=read(),m=read(),p=read();
scanf("%s",s+1);
get_nxt();
kmp();
dp.num[0][0]=1;
g=q_pow(g,n);
dp=dp*g;
for(int i=0;i<m;i++){
ans=(ans+dp.num[0][i])%p;
}
printf("%d",ans);
return 0;
}
Trie(字典树)
把各个字符串连成一棵树,通过标记记录每一个单词,支持插入和查询操作。
结构体封装版本操作:
struct trie{
int nxt[maxn][26],mark[maxn],tot=0;
inline void insert(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
}
pos=nxt[pos][c];
}
mark[pos]=1;
}
inline int find(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
if(!nxt[pos][c]){
return 0;
}
pos=nxt[pos][c];
}
return mark[pos];
}
}t;
例题
1.Phone List
给定 \(t\) 个长度不超过 \(n\) 的数字串,问其中是否存在两个数字串 \(S\) 和 \(T\),使得 \(S\) 是 \(T\) 的前缀,多组数据。
当我们进行 \(\operatorname{insert(s)}\) 的操作时,会判断到是否需要新拓展一个位置 \(nxt(pos,c)\) ,且我们在每个单词的词末都会用 \(mark(pos)\) 标记,那么考虑两种情况(假设 \(S\) 是 \(T\) 的前缀):
- 如果 \(S\) 在 \(T\) 之前先插入字典树,那么我们在插入 \(T\) 时就会检索到 \(S\) 的词尾。
- 如果 \(T\) 在 \(S\) 之前先插入字典树,那么我们在插入 \(S\) 时不会开拓任何一个 \(nxt(pos,c)\),因为所有的 \(S\) 都在已经开拓的 \(T\) 内。
综上,我们维护一个 \(checknew\) 表示是否开拓一个新空间,维护一个 \(checkend\) 表示是否检索到一个词尾,那么当没有开拓新空间或是检索到了词尾时,就找到了符合要求的一对字符串。
注意初始化
struct trie{
int nxt[maxn][26],mark[maxn],tot=0;
void init(){
tot=0;
memset(nxt,0,sizeof(nxt));
memset(mark,0,sizeof(mark));
}
inline bool insert(char *s){
bool checkend=0,checknew=0;
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'0';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
checknew=1;
}
pos=nxt[pos][c];
if(mark[pos]) checkend=1;
}
mark[pos]=1;
return !checknew||checkend;
}
}t;
2.The XOR-largest pair
可以考虑把每个数转换成 \(32\) 位的二进制字符串\(S\),并且把 \(S\) 的每一位都取反得到另一个字符串 \(xorS\),每次插入新的一个 \(S\) 前都在字典树中匹配 \(xorS\) 如果匹配不到则向另一方向匹配,每次匹配成功记录结果,最后维护最大值。
struct trie{
int nxt[maxn][2],tot=0;
inline void insert(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'0';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
}
pos=nxt[pos][c];
}
}
inline int find(char *s){
int len=strlen(s+1),pos=0,ans=0;
for(int i=1;i<=len;i++){
int c=s[i]-'0';
if(nxt[pos][c]){
pos=nxt[pos][c];
ans=ans+(1<<(32-i));
}
else pos=nxt[pos][c^1];
}
return ans;
}
}t;
int n,ansx=minxn;
char s[40],xors[40];
int main(){
n=read();
for(int i=1;i<=n;i++){
int num=read();
for(int j=31;j>=0;j--){
if(num/(1<<j)) s[32-j]='1',xors[32-j]='0';
else s[32-j]='0',xors[32-j]='1';
num%=(1<<j);
}
if(i>1) ansx=max(ansx,t.find(xors));
t.insert(s);
}
printf("%d\n",ansx);
return 0;
}
3.The XOR-longest path
用一遍 \(\operatorname{dfs}\) 遍历出每个节点到根节点路径的异或和,再按照上道题一样求最大的一对值。
4.Nikitosh 和异或
给定一个含 \(N\) 个元素的数组 \(A\),下标从 \(1\) 开始。请找出下面式子的最大值:
\[(A[l_1] \oplus A[l_1+1] \oplus\dots \oplus A[r_1])+(A[l_2] \oplus A[l_2+1] \oplus\dots \oplus A[r_2]) \]其中 \(1\leq l_1\leq r_1\le l2\leq r2\leq N\),\(x\oplus y\) 表示 \(x\) 和 \(y\) 的按位异或。
我们用数组 \(l(i)\) 表示区间 \([1,i]\) 中的最大异或值,\(r(i)\) 表示区间 \([i,N]\) 中的最大异或值,那么显然有:
\[ans=\max_{i=1}^{N} \{l(i)+r(i+1)\} \]那么只需要求得数组 \(l\) 和 \(r\) 就可以了,可以发现异或值同样拥有前缀和的性质,于是每次把 \([1,i]\) 或是 \([i,N]\) 前缀和放到字典树里跑就能得到以 \(i\) 为首元素或是尾元素的最大值,再和 \(l(i-1)\) 或是 \(r(i+1)\) 进行比较,就达到了目的。
struct trie{
int nxt[maxn][2],tot=0;
inline void init(){
memset(nxt,0,sizeof(nxt));
tot=0;
}
inline void insert(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'0';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
}
pos=nxt[pos][c];
}
}
inline int find(char *s){
int ans=0,len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'0';
if(nxt[pos][c]){
pos=nxt[pos][c];
ans=ans+(1<<(32-i));
}
else pos=nxt[pos][c^1];
}
return ans;
}
}t;
int n;
int a[maxn],l[maxn],r[maxn];
char s[40],xors[40];
int ansx=minxn,num=0;
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
num=num^a[i];
int tmp=num;
for(int j=31;j>=0;j--){
if(tmp/(1<<j)) s[32-j]='1',xors[32-j]='0';
else s[32-j]='0',xors[32-j]='1';
tmp%=(1<<j);
}
t.insert(s);
l[i]=max(l[i-1],t.find(xors));
}
num=0;
for(int i=n;i>=1;i--){
num=num^a[i];
int tmp=num;
for(int j=31;j>=0;j--){
if(tmp/(1<<j)) s[32-j]='1',xors[32-j]='0';
else s[32-j]='0',xors[32-j]='1';
tmp%=(1<<j);
}
t.insert(s);
r[i]=max(r[i+1],t.find(xors));
}
for(int i=1;i<=n;i++){
ansx=max(ansx,l[i]+r[i+1]);
}
printf("%d\n",ansx);
return 0;
}
AC自动机(字典图)
原理
类似于在字典树上加上 \(\operatorname{kmp}\) 的操作,这里的指针称之为失配指针 \(fail\),和 \(\operatorname{kmp}\) 不同的是,该指针是建在字典树上,且存在于不同模式串之间。、
fail指针
首先每个 fail[u] 的最坏情况是与根节点相连,最好情况是与父节点的失配指针判断时候匹配,如果不匹配继续向上跳父亲,直到根节点。
queue<int> q;
struct AC_Automaton{
int nxt[maxn][26],mark[maxn],fail[maxn],tot=0;
inline void insert(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
}
pos=nxt[pos][c];
}
mark[pos]++;
}
inline void build(){
for(int i=0;i<26;i++){
if(nxt[0][i]){
fail[nxt[0][i]]=0;
q.push(nxt[0][i]);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(nxt[u][i]){
fail[nxt[u][i]]=nxt[fail[u]][i];
q.push(nxt[u][i]);
}
else{
nxt[u][i]=nxt[fail[u]][i];
}
}
}
}
inline int query(char *s){
int len=strlen(s+1),pos=0,ans=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
pos=nxt[pos][c];
for(int j=pos;j&&~mark[j];j=fail[j]){
ans+=mark[j];
mark[j]=-1;
}
}
return ans;
}
}ac;
int n;
char s[maxm];
int main(){
n=read();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
ac.insert(s);
}
ac.build();
scanf("%s",s+1);
printf("%d\n",ac.query(s));
return 0;
}
记录一下输入的字符串,然后把查询和插入操作改一下。
struct AC_Automaton{
int nxt[maxn][26],mark[maxn],fail[maxn],tot=0;
int ans[maxn];
inline void clear(){
memset(nxt,0,sizeof(nxt));
memset(mark,0,sizeof(mark));
memset(fail,0,sizeof(fail));
memset(ans,0,sizeof(ans));
tot=0;
}
inline void insert(char *s,int ord){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
if(!nxt[pos][c]){
nxt[pos][c]=++tot;
}
pos=nxt[pos][c];
}
mark[pos]=ord;
}
inline void build(){
for(int i=0;i<26;i++){
if(nxt[0][i]){
fail[nxt[0][i]]=0;
q.push(nxt[0][i]);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(nxt[u][i]){
fail[nxt[u][i]]=nxt[fail[u]][i];
q.push(nxt[u][i]);
}
else{
nxt[u][i]=nxt[fail[u]][i];
}
}
}
}
inline void query(char *s){
int len=strlen(s+1),pos=0;
for(int i=1;i<=len;i++){
int c=s[i]-'a';
pos=nxt[pos][c];
for(int j=pos;j;j=fail[j]){
ans[mark[j]]++;
}
}
}
}ac;