OI模板-字符串
字符串哈希
单哈希
给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)
#define M (int)(1515)
const int hash_base=31;
const int hash_mod=998244353;
char str[M];
int n,cnt=1,t[N];
struct hash_str
{
int len,hsh[M],pwd[M];
void Hash(int l,char *str)
{
len=l; pwd[0]=1; hsh[0]=0;
for(int i=1; i<=l; i++)
{
pwd[i]=pwd[i-1]*hash_base%hash_mod;
hsh[i]=(hsh[i-1]*hash_base%hash_mod+str[i])%hash_mod;
}
}
int gethash(int l,int r)
{
int res=(hsh[r]-hsh[l-1]*pwd[r-l+1])%hash_mod;
res=(res+hash_mod)%hash_mod;
return res;
}
}p;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> (str+1);
p.Hash(strlen(str+1),str);
t[i]=p.gethash(1,p.len);
}
sort(t+1,t+1+n);
for(int i=2; i<=n; i++)
if(t[i]!=t[i-1])++cnt;
cout << cnt << '\n';
return 0;
}双哈希
给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+5)
#define hash_cnt 2
const int hash_base[hash_cnt]={29,31};
const int hash_mod[hash_cnt]={1000000007,998244353};
struct hash_str
{
char s[N];
int len,hsh[hash_cnt][N];
int pwd[hash_cnt][N];
void init()
{
len=0;
for(int i=0; i<hash_cnt; i++)
{
hsh[i][0]=0;
pwd[i][0]=1;
}
}
hash_str(){init();}
void add(char ch)
{
s[++len]=ch;
for(int i=0; i<hash_cnt; i++)
{
pwd[i][len]=pwd[i][len-1]*hash_base[i]%hash_mod[i];
hsh[i][len]=(hsh[i][len-1]*hash_base[i]+ch)%hash_mod[i];
}
}
vector<int> gethash(int l,int r)
{
vector<int> res(hash_cnt,0);
for(int i=0; i<hash_cnt; i++)
{
int t=(hsh[i][r]-hsh[i][l-1]*pwd[i][r-l+1])%hash_mod[i];
t=(t+hash_mod[i])%hash_mod[i];
res[i]=t;
}
return res;
}
}s,t;
bool equal(const vector<int> &vec1,const vector<int> &vec2)
{
assert(vec1.size()==vec2.size());
for(int i=0; i<vec1.size(); i++)
if(vec1[i]!=vec2[i])return 0;
return 1;
}
int n;
char str[N];
void solve(char *str)
{
int len=strlen(str+1);
t.init();
for(int i=1; i<=len; i++)
t.add(str[i]);
int d=1;
for(int j=min(len,s.len); j>=1; j--)
if(equal(t.gethash(1,j),s.gethash(s.len-j+1,s.len)))
{d=j+1;break;}
for(int i=d; i<=len; i++)
s.add(str[i]);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> str+1;
solve(str);
}
cout << s.s+1 << endl;
return 0;
}KMP
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n+m)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e6+5)
int n,m,fail[MAXN];
char t[MAXN],s[MAXN];
signed main()
{
scanf("%s\n%s\n",t+1,s+1);
n=strlen(t+1);m=strlen(s+1);
for(int i=2,j=0; i<=m; i++)
{
while(j&&s[i]!=s[j+1])j=fail[j];
if(s[i]==s[j+1])++j;
fail[i]=j;
}
for(int i=1,j=0; i<=n; i++)
{
while(j&&t[i]!=s[j+1])j=fail[j];
if(t[i]==s[j+1])++j;
if(j==m)printf("%lld\n",i-m+1);
}
for(int i=1; i<=m; i++)
printf("%lld%c",fail[i]," \n"[i==m]);
return 0;
}ExKMP（Z 函数）
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n+m)\)
b 与 b的后缀 的最大前缀、b 与 a的后缀 的最大前缀
注意该代码多测需要清空！
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e7+5)
char a[N],b[N];
int z[N],p[N],n,m;
int ans1,ans2;
void exkmp()
{
z[1]=m;
for(int i=2,l=0,r=0; i<=m; i++)
{
if(i<=r)z[i]=min(r-i+1,z[i-l+1]);
while(i+z[i]<=m&&b[i+z[i]]==b[z[i]+1])++z[i];
if(i+z[i]-1>=r)l=i,r=i+z[i]-1;
}
for(int i=1,l=0,r=0; i<=n; i++)
{
if(i<=r)p[i]=min(r-i+1,z[i-l+1]);
while(i+p[i]<=n&&a[i+p[i]]==b[p[i]+1])++p[i];
if(i+p[i]-1>=r)l=i,r=i+p[i]-1;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> a+1 >> b+1;
n=strlen(a+1);m=strlen(b+1);
exkmp();
int res=0;
for(int i=1; i<=m; i++)res^=i*(z[i]+1);
cout << res << endl;
res=0;
for(int i=1; i<=n; i++)res^=i*(p[i]+1);
cout << res << endl;
return 0;
}Manacher
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
内存105.53MB（比较极限的数据）
aabaa
#a#a#b#a#a#
# a # a # b # a # a #
1 2 3 2 1 6 1 2 3 2 1#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1.1e7+15)
char s[N<<1];
int n,p[N<<1];
void Manacher(int l)
{
int r=1,mid=1,ans=0;
for(int i=1; i<=l; i++)
{
p[i]=(i<=r)?min(p[(mid<<1)-i],r-i+1):1;
while(s[i-p[i]]==s[i+p[i]]) ++p[i];
if(i+p[i]-1>r)r=i+p[i]-1,mid=i;
// 这里如果写 i+p[i]-1>=r 则会在r相等时优先更新mid
// 对p数组的求解没有影响，但是在某些题目中会出现问题
ans=max(ans,p[i]-1);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> (s+1); n=strlen(s+1);
for(int i=n; i; i--)
s[i*2]=s[i],s[i*2+1]='#';
s[0]='$';s[1]='#';
Manacher(n*2+1);
return 0;
}Trie
这个是老版本的（The XOR Largest Pair），太简单了不写一遍了，详见AC自动机即可
时间复杂度 \(O(\max{\{|s_i|\}})\)
空间复杂度 \(O(k\sum |s_i|),k\) 为字符集范围
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e5+5)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>inline void read(T &k)
{
char ch=getchar();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){putchar('-');k=-k;}
if(k>9)write(k/10);
putchar(k%10+'0');
}
int n,ans=0;
int a[MAXN];
struct Trie
{
int trie[MAXN*32][3],tot=1; // trie的大小要注意
void insert(int x)
{
int p=0;
for(int i=31; i>=0; --i) // 其实只要30就可以了
{
int k=(x>>i)&1;
if(!trie[p][k])trie[p][k]=++tot;
p=trie[p][k];
}
}
int qry(int x)
{
int ans=0,p=0;
for(int i=31; i>=0; --i)
{
int k=(x>>i)&1;
if(trie[p][k^1])p=trie[p][k^1],ans|=(1<<i); // 尽可能选择这一位相反的
else p=trie[p][k];
}
return ans;
}
}t[1]; // 这个[1]并没有什么用 qwq
signed main()
{
read(n);
for(int i=1; i<=n; i++)
{
read(a[i]);
t[0].insert(a[i]);
ans=max(ans,t[0].qry(a[i]));
}
write(ans);putchar('\n');
return 0;
}
01Trie
封装版
int n,a[N],res[N];
struct Trie
{
int tot,trie[L][2],ed[L];
void clear()
{
tot=0;
memset(trie,0,sizeof(trie));
memset(ed,0,sizeof(ed));
}
void insert(int i)
{
int u=0, x=a[i];
for(int j=30,c; j>=0; j--)
{
c = (x >> j) & 1;
if(!trie[u][c]) trie[u][c]=++tot;
u=trie[u][c];
}
ed[u]=i;
}
// find max{x xor a[j]} (j ≠ i)
int query(int x)
{
int u=0;
for(int j=30,c; j>=0; j--)
{
c = (x >> j) & 1;
if(trie[u][c^1]) u=trie[u][c^1];
else if(trie[u][c]) u=trie[u][c];
}
return a[ed[u]];
}
}tr;AC自动机
这个 AC 自动机的模板题在洛谷搞了3个属实离谱
简单来说，第一个就是建自动机+暴力跑 fail 树算答案，第三个就是建自动机+高级的方式算答案。
建议直接看 AC 自动机（二次加强版），以及后面的高级写法
AC自动机（简单版）
时间复杂度 \(O\left(\sum|s_i|+n|\Sigma| + |S|\right)\) ，\(n \le \sum|s_i|\) 表示节点数
如果不连 trie 图，并且在构建 fail 指针的时候避免遍历到空儿子，时间复杂度就是 \(\mathcal{O}(\sum|s_i| + |S|)\)
空间复杂度 \(O(|\Sigma|\cdot\sum |s_i| + |S|)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e6+5)
int n;
queue<int>q;
char tmp[MAXN],t[MAXN];
int trie[MAXN][28],e[MAXN],tot,fail[MAXN];
void insert(int l,char *s)
{
int p=0;
for(int i=1; i<=l; i++)
{
int c=s[i]-'a';
if(!trie[p][c])trie[p][c]=++tot;
p=trie[p][c];
}
++e[p];
}
void build()
{
for(int i=0; i<26; i++)
if(trie[0][i])q.push(trie[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0; i<26; i++)
{
if(trie[u][i])
{
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else trie[u][i]=trie[fail[u]][i];
}
}
}
int query(int l,char *t)
{
int res=0,u=0;
for(int i=1; i<=l; i++)
{
u=trie[u][t[i]-'a'];
for(int j=u; j&&e[j]!=-1; j=fail[j])
res+=e[j],e[j]=-1;
}
return res;
}
signed main()
{
scanf("%lld",&n);
for(int i=1; i<=n; i++)
{
scanf("%s",tmp+1);
insert(strlen(tmp+1),tmp);
}
scanf("%s",t+1);
build();
printf("%lld\n",query(strlen(t+1),t));
return 0;
}AC自动机（加强版）
最坏时间复杂度 \(O(T|S|\max\{|s_i|\})\)
空间复杂度 \(O(|\Sigma|\cdot\sum |s_i| + |S|)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)(155)
#define S (int)(75)
#define SZ (int)(155*75)
#define L (int)(1e6+5)
char t[L],s[N][S];
int n,cnt[N],e[SZ],val[SZ];
int trie[SZ][32],tot,fail[SZ];
void init()
{
memset(fail,0,sizeof(fail));
memset(cnt,0,sizeof(cnt));
memset(e,0,sizeof(e));
memset(trie,0,sizeof(trie));
memset(val,0,sizeof(val));
tot=0;
}
void insert(int l,char *s,int id)
{
int u=0;
for(int i=1; i<=l; i++)
{
int c=s[i]-'a';
if(!trie[u][c])trie[u][c]=++tot;
u=trie[u][c];
}
e[u]=id;
}
queue<int>q;
void build()
{
for(int i=0; i<26; i++)
if(trie[0][i])q.push(trie[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0; i<26; i++)
{
if(trie[u][i])
{
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else trie[u][i]=trie[fail[u]][i];
}
}
}
int AC(int l,char *t)
{
int u=0,res=0;
for(int i=1; i<=l; i++)
{
u=trie[u][t[i]-'a'];
for(int j=u; j; j=fail[j])
++val[j];
}
for(int i=1; i<=tot; i++) if(e[i])
{
res=max(res,val[i]);
cnt[e[i]]=val[i];
}
return res;
}
signed main()
{
while(scanf("%lld",&n)&&n)
{
init();
for(int i=1; i<=n; i++)
{
scanf("%s\n",s[i]+1);
insert(strlen(s[i]+1),s[i],i);
}
scanf("%s\n",t+1);
build();
int mx=AC(strlen(t+1),t);
printf("%lld\n",mx);
for(int i=1; i<=n; i++)
if(cnt[i]==mx)printf("%s\n",s[i]+1);
}
return 0;
}AC自动机（二次加强版）
时间复杂度 \(O\left(\sum|s_i|+n|\Sigma| + |S|\right)\) ，\(n \le \sum|s_i|\) 表示节点数
如果不连 trie 图，并且在构建 fail 指针的时候避免遍历到空儿子，时间复杂度就是 \(\mathcal{O}(\sum|s_i| + |S|)\)
空间复杂度 \(O(|\Sigma|\cdot\sum |s_i| + |S|)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)(2e5+5)
#define L (int)(2e6+5)
char t[L],s[N];
int n,ans[N],e[N],val[N],in[N];
int trie[N][32],tot,fail[N],f[N];
void init(){for(int i=1; i<=n; i++)f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){f[find(u)]=find(v);}
void insert(int l,char *s,int id)
{
int u=0;
for(int i=1; i<=l; i++)
{
int c=s[i]-'a';
if(!trie[u][c])trie[u][c]=++tot;
u=trie[u][c];
}
if(!e[u])e[u]=id;
else merge(id,e[u]);
}
queue<int>q;
void build()
{
for(int i=0; i<26; i++)
if(trie[0][i])q.push(trie[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0; i<26; i++)
{
if(trie[u][i])
{
fail[trie[u][i]]=trie[fail[u]][i];
++in[trie[fail[u]][i]];
q.push(trie[u][i]);
}else trie[u][i]=trie[fail[u]][i];
}
}
}
void AC(int l,char *t)
{
int u=0;
for(int i=1; i<=l; i++)
{
u=trie[u][t[i]-'a'];
++val[u];
}
for(int i=1; i<=tot; i++)
if(!in[i])q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
if(e[u])ans[e[u]]=val[u];
val[fail[u]]+=val[u];
if(!--in[fail[u]])q.push(fail[u]);
}
}
signed main()
{
scanf("%lld",&n); init();
for(int i=1; i<=n; i++)
{
scanf("%s\n",s+1);
insert(strlen(s+1),s,i);
}
scanf("%s\n",t+1);
build();
AC(strlen(t+1),t);
for(int i=1; i<=n; i++)
printf("%lld\n",ans[find(i)]);
return 0;
}线性构建AC自动机
这是做 P9089 时，在题解区看到的高级写法
众所周知，我们一般的建图都是建的“字典图”，而这种方式是直接建 字典树+fail树
直接搬原题代码了
时间复杂度 \(\mathcal{O}(\sum |s_i|)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
int n,f[N],g[N],dep[N]; string s[N];
int pos = 1,tot,fa[N],head[N],fail[N],tr[N][26];
struct Edge { int u,v,c,next; } e[N];
void addEdge(int u,int v,int c)
{
tr[u][c] = v; fa[v] = u; dep[v] = dep[u] + 1;
e[++pos] = {u,v,c,head[u]}; head[u] = pos;
}
void insert(string s)
{
int u = 0, l = s.size();
for(int i = 0; i < l; i++)
{
int c = s[i] - 'a';
if(!tr[u][c]) addEdge(u, ++tot, c);
u = tr[u][c];
}
}
void build()
{
queue<pii> q;
for(int i = 0; i < 26; i++) if(tr[0][i]) q.push({tr[0][i], i});
while(!q.empty())
{
int u,c,x; tie(u,c) = q.front(); q.pop();
for(x = fail[fa[u]]; x && !tr[x][c]; x = fail[x]);
if(x != fa[u]) fail[u] = tr[x][c];
g[u] = fail[u] ? g[fail[u]] : dep[u];
for(int i = head[u]; i; i = e[i].next) q.push({e[i].v, e[i].c});
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
reverse(s[i].begin(), s[i].end()); insert(s[i]);
}
build(); int res = 0;
for(int o = 1; o <= n; o++)
{
int m = s[o].size(), u = 0; f[0] = 0;
for(int i = 1; i <= m; i++)
{
u = tr[u][s[o][i - 1] - 'a'];
f[i] = f[i - g[u]] + 1; res += f[i];
}
}
cout << res << '\n';
return 0;
}
后缀数组 SA
计数排序实现是 \(O(n\log n)\) ，直接 sort 是 \(O(n\log^2 n)\)
实测 \(n \le 10^6\) 时直接 sort 稍微慢一些，不过相对容易理解。
sa[i] 表示将排名第 \(i\) 的后缀（排名：所有后缀排序后第 \(i\) 小）
rk[i] 表示后缀 \(i\)
的排名，满足 sa[rk[i]] = rk[sa[i]] = i 。
计数排序版本：
// 2024年06月05日 15:04:10
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])
char s[N];
int n, m, sa[N], rk[N * 2], tmp[N * 2], cnt[N];
void sort(int w)
{
memset(cnt, 0, sizeof(int) * (m + 1));
for(int i = 1; i <= n; i++) tmp[i] = sa[i];
for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> (s + 1); n = strlen(s + 1); m = max(n, 333); // m 是 rk 的值域
for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
for(int w = 1; w < n; w *= 2)
{
sort(w); sort(0);
for(int i = 1; i <= n; i++) tmp[i] = rk[i];
for(int i = 1, p = 0; i <= n; i++)
if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
}
for(int i = 1; i <= n; i++) cout << sa[i] << " \n"[i == n];
return 0;
}sort 版本：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])
char s[N];
int n, w, sa[N], rk[N * 2], tmp[N * 2];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> (s + 1); n = strlen(s + 1);
for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
for(w = 1; w < n; w *= 2)
{
sort(sa + 1, sa + 1 + n, [](int x, int y) {
return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
});
for(int i = 1; i <= n; i++) tmp[i] = rk[i];
for(int i = 1, p = 0; i <= n; i++)
if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
}
for(int i = 1; i <= n; i++) cout << sa[i] << " \n"[i == n];
return 0;
}后缀自动机 SAM
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
// 2024年06月13日 22:03:17
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(ll &x, ll y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))
ll res; char s[N];
int tot, lst, dep[N]; vector<int> vec[N];
struct SAMnode { int ch[26], len, fa; } t[N];
void insert(const int c)
{
int p = lst, now = lst = ++tot;
t[now].len = t[p].len + 1; dep[now] = 1;
while(p > 0 && !t[p].ch[c]) { t[p].ch[c] = now; p = t[p].fa; }
if(!p) { t[now].fa = 1; return; }
int son = t[p].ch[c];
if(t[son].len == t[p].len + 1) t[now].fa = son;
else
{
t[++tot] = t[son]; t[tot].len = t[p].len + 1;
t[son].fa = t[now].fa = tot;
while(p > 0 && t[p].ch[c] == son) { t[p].ch[c] = tot; p = t[p].fa; }
}
}
void dfs(int u)
{
for(int v : vec[u]) { dfs(v), dep[u] += dep[v]; }
if(dep[u] != 1) up(res, (ll)dep[u] * t[u].len);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> (s + 1); tot = lst = 1;
for(int i = 1; s[i]; i++) insert(s[i] - 'a');
for(int i = 2; i <= tot; i++) vec[t[i].fa].push_back(i);
dfs(1); cout << res << '\n';
return 0;
}广义后缀自动机 ExSAM
之前看到巨佬的一个hack，还不确定我这个对不对
这里是讨论 link
时间复杂度 \(O(n|\Sigma|)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e6+15)
#define M (int)(1e6+15)
struct trie_node
{
signed ch[26],fa,val;
}tr[M];
struct SAM_node
{
signed ch[26],len,fa;
}sam[N];
string s;
int n,cnt=1,tot=1,lst=1,pos[N];
void insert(string s)
{
int p=1;
for(int i=0; i<s.size(); i++)
{
int c=s[i]-'a';
if(!tr[p].ch[c])
{
tr[p].ch[c]=++cnt;
tr[cnt].fa=p;
tr[cnt].val=c;
}
p=tr[p].ch[c];
}
}
int update(int c,int lst)
{
int p=lst,now=lst=++tot;
sam[now].len=sam[p].len+1;
for(; p&&!sam[p].ch[c]; p=sam[p].fa)
sam[p].ch[c]=now;
if(!p)sam[now].fa=1;
else
{
int q=sam[p].ch[c];
if(sam[q].len==sam[p].len+1)
sam[now].fa=q;
else
{
int clone=++tot;
sam[clone]=sam[q];
sam[clone].len=sam[p].len+1;
sam[q].fa=sam[now].fa=clone;
for(; p&&sam[p].ch[c]==q; p=sam[p].fa)
sam[p].ch[c]=clone;
}
}
return now;
}
queue<int> q;
void build()
{
for(int i=0; i<26; i++)
if(tr[1].ch[i])q.push(tr[1].ch[i]);
pos[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
pos[u]=update(tr[u].val,pos[tr[u].fa]);
for(int i=0; i<26; i++)
if(tr[u].ch[i])q.push(tr[u].ch[i]);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1; i<=n; i++)
cin >> s,insert(s);
build();
int res=0;
for(int i=2; i<=tot; i++)
res+=sam[i].len-sam[sam[i].fa].len;
cout << res << endl;
return 0;
}回文自动机 PAM
时间复杂度 \(O(n)\)
// 2024年05月31日 20:03:37
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))
char s[N];
int ans, tot, fail[N], len[N], cnt[N], ch[N][26];
int getfail(int p, int i)
{
while(s[i - len[p] - 1] != s[i]) p = fail[p];
return p;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> (s + 1); fail[tot = 1] = 0; len[0] = -1;
for(int i = 1, p, c; s[i]; i++)
{
if(i > 1) s[i] = (s[i] + ans - 97) % 26 + 97;
c = s[i] - 'a'; p = i > 1 ? getfail(p, i) : 0;
if(!ch[p][c])
{
ch[p][c] = ++tot; len[tot] = len[p] + 2;
fail[tot] = p > 0 ? ch[getfail(fail[p], i)][c] : 1;
cnt[tot] = cnt[fail[tot]] + 1;
}
p = ch[p][c]; ans = cnt[p]; cout << ans << ' ';
}
return 0;
}子序列自动机
朴素构建
过不了模板题，但是在一些题目里可以很方便写出来。
时间复杂度 \(\mathcal{O}(n |\Sigma|)\)
for(int i = len - 1; ~i; i--) {
for(int j = 0; j < 26; j++) ch[i][j] = ch[i + 1][j];
ch[i][s[i + 1] - 'a'] = i + 1;
}可持久化线段树构建
时间复杂度 \(\mathcal{O}(n \log |\Sigma|+ \sum l_i \log |\Sigma|)\) ，其中 \(\sum l_i\) 表示询问序列的总长度。
// 2024年06月08日 14:10:02
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int a[N], b[N];
struct Tree
{
Tree *ls, *rs; int l, r, v;
// build
Tree(int _l, int _r) : l(_l), r(_r), v(-1)
{
if(l != r)
{
int mid = (l + r) >> 1;
ls = new Tree(l, mid); rs = new Tree(mid + 1, r);
}
}
// Modify
Tree(Tree *pre, int x, int _v) : l(pre -> l), r(pre -> r), v(0)
{
if(l == r) v = _v;
else
{
if(x <= pre -> ls -> r) {
rs = pre -> rs; ls = new Tree(pre -> ls, x, _v);
}else {
ls = pre -> ls; rs = new Tree(pre -> rs, x, _v);
}
}
}
int query(int x)
{
if(l == r) return v;
if(x <= ls -> r) return ls -> query(x);
else return rs -> query(x);
}
} *rt[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int _, n, q, m; cin >> _ >> n >> q >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
rt[n] = new Tree(1, m);
for(int i = n; i; i--) rt[i - 1] = new Tree(rt[i], a[i], i);
for(int len, pos; q--; )
{
pos = 0; cin >> len;
for(int i = 1; i <= len; i++) cin >> b[i];
for(int i = 1; i <= len; i++)
{
pos = rt[pos] -> query(b[i]);
if(pos == -1) break;
}
cout << ((~pos) ? "Yes" : "No") << '\n';
}
return 0;
}vector + 二分
实际上模板题可以直接二分
时间复杂度 \(\mathcal{O}(n+ \sum l_i \log |\Sigma|)\) ，其中 \(\sum l_i\) 表示询问序列的总长度。
// 2024年06月08日 14:18:17
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define upper(a, b) upper_bound(a.begin(), a.end(), b)
#define N ((int)(1e5 + 15))
int a[N], b[N];
vector<int> pos[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int _, n, q; cin >> _ >> n >> q >> _;
for(int i = 1; i <= n; i++) { cin >> a[i], pos[a[i]].push_back(i); }
for(int p = 0, len; q--; )
{
cin >> len; p = 0; bool ok = true;
for(int i = 1; i <= len; i++) cin >> b[i];
for(int i = 1; i <= len; i++)
{
auto nxt = upper_bound(pos[b[i]].begin(), pos[b[i]].end(), p);
if(nxt == pos[b[i]].end()) { ok = false; break; } else p = *nxt;
}
cout << (ok ? "Yes" : "No") << '\n';
}
return 0;
}
