登录
← 返回首页 | 代码片段 › 6 字符串 › 字符串 / 搜索
JSON MD

6 字符串

含 31 个代码片段
KMP kmp 6.6.1 KMP
40 行
CPP JSON
【KMP(Knuth-Morris-Pratt)字符串匹配算法】 ▪ buildNext(pattern) — 构建 next 数组(前缀函数):对模式串每个位置 i,计算以 i 结尾的最长公共前后缀长度。失配时 j=next[j-1] 回退,O(M) ▪ search(text, pattern) — 在 text 中搜索 pattern:双指针扫描,匹配时 i++,j++;失配时若 j>0 则 j=next[j-1] 否则 i++,O(N+M) 无回溯匹配,效率远高于暴力。适用于单模式串匹配、字符串周期分析、最小循环节计算。
C++ 40 行 CPP
// KMP算法:构建next数组
vector<int> buildNext(const string& pattern) {
    int n = pattern.size();
    vector<int> next(n, 0);
    int j = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// KMP算法:在文本中查找模式串,返回所有匹配的起始位置
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> result;
    int n = text.size();
    int m = pattern.size();
    if (m == 0) return result;
    
    vector<int> next = buildNext(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            result.push_back(i - m + 1);
            j = next[j - 1];
        }
    }
    return result;
}
KMP kmp 6.6.1 KMP
22 行
CPP JSON
【KMP】 KMP(Knuth-Morris-Pratt)字符串匹配模板,失配时利用前缀函数快速回退。 复杂度:预处理 O(M),匹配 O(N+M)
C++ 21 行 CPP
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int i,j,n,m,next[1000005];string a,b;
int main(){
	cin>>a>>b;
	n=a.size();a='$'+a;
	m=b.size();b='$'+b;
	for(i=2,j=0;i<=m;i++){
		while(j&&b[i]!=b[j+1])j=next[j];
		if(b[i]==b[j+1])j++;
		next[i]=j;
	}
	for(i=1,j=0;i<=n;i++){
		while(j&&a[i]!=b[j+1])j=next[j];
		if(a[i]==b[j+1])j++;
		if(j==m){j=next[j];printf("%d\n",i-m+1);}
	}
	for(i=1;i<=m;i++)printf("%d ",next[i]);
}
manacher 标准700ms 6.6.2 Manacher
18 行
CPP JSON
luogu-judger-enable-o2
C++ 17 行 CPP
// luogu-judger-enable-o2
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=22000003;
char a[N]={'$','|'},c=getchar();int r[N],mid,ans,R,n=1,i;
int main(){
    while(c>='a'&&c<='z')a[++n]=c,a[++n]='|',c=getchar();
    for(i=1;i<=n;i++){
        if(i<=R)r[i]=min(r[(mid<<1)-i],R-i+1);
        else r[i]=1;
        while(a[i-r[i]]==a[i+r[i]])r[i]++;
        if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
        ans=max(ans,r[i]-1);
    }
    printf("%d",ans);
}
manacher(仅适用于找最长回文长度) 玄学150ms 6.6.2 Manacher
15 行
CPP JSON
luogu-judger-enable-o2
C++ 14 行 CPP
// luogu-judger-enable-o2
#include<cstdio>
char a[11550000]={'$'};int T,i,s,l,r;
int main(){
    gets(a+1);
    for(i=1;a[i];++i){
        l=r=i;
        while(a[i]==a[r+1])++r;
        i=r;
        while(a[r+1]==a[l-1])++r,--l;
        if(r-l+1>s)s=r-l+1;
    }
    printf("%d",s);
}
Trie树 于是他错误的点名开始了 6.6.3 Trie
40 行
CPP JSON
【Trie树(于是他错误的点名开始了)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void add(char ch[]) — 加法更新 int find(char ch[]) — 查找(并查集寻根/二分查找)
C++ 39 行 CPP
#pragma once
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
const int SP=500003;
int trie[SP][26],pan[SP],ed[SP],re,t=1,n;
char ch[55];
inline void add(char ch[]){
    R a,i=0,p=1,m=strlen(ch);
    for(;i<m;i++){
        a=ch[i]-'a';
        if(!trie[p][a])trie[p][a]=++t;
        p=trie[p][a];
    }
    ed[p]=1;
}
inline int find(char ch[]){
    R re,i=0,p=1,m=strlen(ch);
    for(;i<m;i++){
        p=trie[p][ch[i]-'a'];
        if(!p)return 0;
    }
    re=ed[p];
    if(ed[p])ed[p]++;
    return re;
}
int main(){
    scanf("%d",&n);
    while(n--){scanf("%s",ch);add(ch);}
    scanf("%d",&n);
    while(n--){
        scanf("%s",ch);
        re=find(ch);
        if(!re)printf("WRONG\n");
        else if(re==1)printf("OK\n");
        else printf("REPEAT\n");
    }
}
Trie树 前缀统计 6.6.3 Trie
30 行
CPP JSON
【Trie树(前缀统计)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void add(char ch[]) — 加法更新 int find(char ch[]) — 查找(并查集寻根/二分查找)
C++ 29 行 CPP
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
const int SP=500003;
int trie[SP][26],pan[SP],ed[SP],re,t=1,n,m;char ch[55];
inline void add(char ch[]){
    R a,i=0,p=1,l=strlen(ch);
    for(;i<l;i++){
        a=ch[i]-'a';
        if(!trie[p][a])trie[p][a]=++t;
        p=trie[p][a];
    }
    ++ed[p];
}
inline int find(char ch[]){
    R i=0,p=1,ans=0,l=strlen(ch);
    for(;i<l;i++){
        p=trie[p][ch[i]-'a'];
        ans+=ed[p];
        if(!p)return ans;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    while(n--){scanf("%s",ch);add(ch);}
    while(m--){scanf("%s",ch);printf("%d\n",find(ch));}
}
可持久化Trie树 最大异或和 6.6.3 Trie
41 行
CPP JSON
【可持久化Trie树(最大异或和)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re p,Re q,Re o,Re x) — 插入元素 int ask(Re p,Re q,Re o,Re x) — 核心算法函数 核心结构体:Trie 关键配置: N=6e5+5,logN=24 说明:freopen("123.txt","r",stdin);
C++ 40 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=6e5+5,logN=24;
int n,x,y,z,T,A[N],pt[N];char op;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Trie{
	int O,cnt[N*(logN+2)],tr[N*(logN+2)][2];
	inline void insert(Re p,Re q,Re o,Re x){
		if(o<0)return;Re i=(x>>o)&1;
		tr[p][i]=++O,tr[p][i^1]=tr[q][i^1];
		cnt[tr[p][i]]=cnt[tr[q][i]]+1;
		insert(tr[p][i],tr[q][i],o-1,x);
	}
	inline int ask(Re p,Re q,Re o,Re x){
		if(o<0)return 0;Re i=(x>>o)&1;
		if(cnt[tr[q][i^1]]>cnt[tr[p][i^1]])return (1<<o)+ask(tr[p][i^1],tr[q][i^1],o-1,x);
		else return ask(tr[p][i],tr[q][i],o-1,x);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(A[i]),A[i]^=A[i-1],T1.insert(pt[i]=++T1.O,pt[i-1],logN,A[i]);
	T1.insert(pt[0]=++T1.O,0,logN,0);
	while(T--){
		scanf(" %c",&op),in(x);
		if(op=='A')++n,A[n]=A[n-1]^x,T1.insert(pt[n]=++T1.O,pt[n-1],logN,A[n]);
		else in(y),in(z),--x,--y,printf("%d\n",T1.ask(x?pt[x-1]:0,pt[y],logN,z^A[n]));
	}
}
Snowflake Snow Snowflakes 最小表示法+Hash 6.6.4 字符串Hash
44 行
CPP JSON
【Snowflake Snow Snowflakes(最小表示法+Hash)】 字符串哈希(String Hashing)模板,将字符串映射为整数便于快速比较。 核心函数: int sakura(int a[]) — 后缀数组 uLL Hash(int a[],int st) — 哈希计算 uLL find(int a[]) — 查找(并查集寻根/二分查找) 适用场景:字符串匹配、回文检测、子串统计、字典树检索
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<map>
#define R register int
#define uLL long long
int n,t,p=13333331,re,A[13];
std::map<uLL,int>pan;
inline int sakura(int a[]){
    R i=1,j=2,k;
    while(i<=6&&j<=6){
        k=0;
        while(k<6&&a[i+k]==a[j+k])++k;
        if(k==6)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline uLL Hash(int a[],int st){
    R i=0;uLL x=0;
    for(;i<6;++i)x=x*p+(uLL)a[st+i];
    return x;
}
inline uLL find(int a[]){
    R x,y,i=1,k=0,b[13];
    for(;i<=6;i++)b[i]=a[7-i];
    for(i=1;i<=6;i++)a[i+6]=a[i],b[i+6]=b[i];
	x=sakura(a),y=sakura(b);
    for(i=0;i<6;i++)
		if(a[x+i]<b[y+i])return Hash(a,x);
		else if(a[x+i]>b[y+i])return Hash(b,y);
    return Hash(a,x);
}
int main(){
    scanf("%d",&n);R i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=6;j++)scanf("%d",&A[j]);
        uLL re=find(A);
        if(pan[re]){printf("Twin snowflakes found.");return 0;}
    	pan[re]=1;
	}
    printf("No two snowflakes are alike.");
}
字符串Hash表 兔子与兔子 6.6.4 字符串Hash
20 行
CPP JSON
【字符串Hash表(兔子与兔子)】 字符串哈希(String Hashing)模板,将字符串映射为整数便于快速比较。 核心函数: LL Hash(int l,int r) — 哈希计算 关键配置: N=1e6+5 适用场景:字符串匹配、回文检测、子串统计、字典树检索
C++ 19 行 CPP
#include<iostream>
#include<string>
#include<cstdio>
#define LL long long
using namespace std;
const int N=1e6+5;
int l1,r1,l2,r2,n,m,i,p=27;
LL f[N],mi[N];string a;
inline LL Hash(int l,int r){return f[r]-f[l-1]*mi[r-l+1];}
int main(){
    cin>>a;n=a.size();a='$'+a;mi[0]=1;
    for(i=1;i<=n;i++)f[i]=f[i-1]*p+a[i]-'a'+1,mi[i]=mi[i-1]*p;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(Hash(l1,r1)==Hash(l2,r2))printf("Yes\n");
        else printf("No\n");
    }
}
Necklace 最小表示法判断同构 6.6.5 最小表示法
27 行
CPP JSON
【Necklace(最小表示法判断同构)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: int sakura(char a[]) — 后缀数组 int judge(char a[],char b[]) — 判定函数
C++ 26 行 CPP
#include<cstring>
#include<cstdio>
int i,j,k,n,m,x,y,st;char a[2000003],b[2000003];
inline int sakura(char a[]){
    i=1,j=2;
    while(i<=n&&j<=n){
        k=0;
        while(k<n&&a[i+k]==a[j+k])++k;
        if(k==n)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline int judge(char a[],char b[]){
    n=strlen(a+1);
    for(i=1;i<=n;++i)a[i+n]=a[i],b[i+n]=b[i];
    x=sakura(a),y=sakura(b);
    a[x+n]=b[y+n]='\0';
    return !strcmp(a+x,b+y);
}
int main(){
    scanf("%s%s",a+1,b+1);
    if(judge(a,b)){printf("Yes\n");puts(a+x);}
    else printf("No");
}
Snowflake Snow Snowflakes 最小表示法+Hash 6.6.5 最小表示法
44 行
CPP JSON
【Snowflake Snow Snowflakes(最小表示法+Hash)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: int sakura(int a[]) — 后缀数组 uLL Hash(int a[],int st) — 哈希计算 uLL find(int a[]) — 查找(并查集寻根/二分查找)
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<map>
#define R register int
#define uLL long long
int n,t,p=13333331,re,A[13];
std::map<uLL,int>pan;
inline int sakura(int a[]){
    R i=1,j=2,k;
    while(i<=6&&j<=6){
        k=0;
        while(k<6&&a[i+k]==a[j+k])++k;
        if(k==6)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline uLL Hash(int a[],int st){
    R i=0;uLL x=0;
    for(;i<6;++i)x=x*p+(uLL)a[st+i];
    return x;
}
inline uLL find(int a[]){
    R x,y,i=1,k=0,b[13];
    for(;i<=6;i++)b[i]=a[7-i];
    for(i=1;i<=6;i++)a[i+6]=a[i],b[i+6]=b[i];
	x=sakura(a),y=sakura(b);
    for(i=0;i<6;i++)
		if(a[x+i]<b[y+i])return Hash(a,x);
		else if(a[x+i]>b[y+i])return Hash(b,y);
    return Hash(a,x);
}
int main(){
    scanf("%d",&n);R i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=6;j++)scanf("%d",&A[j]);
        uLL re=find(A);
        if(pan[re]){printf("Twin snowflakes found.");return 0;}
    	pan[re]=1;
	}
    printf("No two snowflakes are alike.");
}
最小表示法 工艺 6.6.5 最小表示法
30 行
CPP JSON
【最小表示法(工艺)】 最小表示法模板,求字符串循环同构的最小字典序表示。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=3e5+5
C++ 29 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5;
int n,s[N<<1];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(s[i]),s[i+n]=s[i];
	Re i=1,j=2;
	while(i<=n&&j<=n){
		Re k=1;
		while(k<=n&&s[i+k-1]==s[j+k-1])++k;
		if(k>n)break;
		if(s[i+k-1]>s[j+k-1])i+=k;
		else j+=k;
		if(i==j)++i;
	}
	Re st=min(i,j);
	for(Re i=0;i<n;++i)printf("%d ",s[st+i]);
}
Cyclical Quest 暴力解法-广义SAM不加特判会MLE 6.6.6 AC自动机与后缀数组
83 行
CPP JSON
【Cyclical Quest(暴力解法-广义SAM不加特判会MLE)】 字符串高级算法模板。 核心函数: void in(Re &x) — 核心算法函数 int insert(Re ch,Re op,Re last) — 插入元素 void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) int ask(Re p,Re len) — 核心算法函数 核心结构体:Suffix_Automaton, QAQ 关键配置: N=3e6+5,M=1e6+3,logN=21 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 82 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=3e6+5,M=1e6+3,logN=21;
int n,T,len[M],vis[N<<1],tmp[N<<1];LL ans;char s[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
vector<int>Q[M];
struct Suffix_Automaton{
	int O,last,siz[N<<1],link[N<<1],maxlen[N<<1];map<int,int>trans[N<<1];
	Suffix_Automaton(){O=1;}
	inline int insert(Re ch,Re op,Re last){
		if(trans[last].find(ch)!=trans[last].end()){
			Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])return x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(map<int,int>::iterator it=trans[x].begin();it!=trans[x].end();++it)trans[y].insert(*it);
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                return y;
            }
		}
		Re z=++O,p=last;if(op)siz[z]=1;maxlen[z]=maxlen[p]+1;
		while(p&&trans[p].find(ch)==trans[p].end())trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			Re x=trans[p][ch];
			if(maxlen[x]==maxlen[p]+1)link[z]=x;
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				for(map<int,int>::iterator it=trans[x].begin();it!=trans[x].end();++it)trans[y].insert(*it);
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[x]=link[z]=y;
			}
		}
		return z;
	}
	int o,head[N<<1];
	struct QAQ{int to,next;}a[N<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		for(Re i=head[x];i;i=a[i].next)dfs(a[i].to),siz[x]+=siz[a[i].to];
	}
	inline void build(){
		for(Re i=2;i<=O;++i)add(link[i],i);dfs(1);
	}
	inline int ask(Re p,Re len){
		while(maxlen[link[p]]>=len)p=link[p];return p;
	}
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    scanf("%s",s+1),n=strlen(s+1),in(T);
    for(Re i=1,last=1;s[i];++i)last=SAM.insert(s[i]-'a',1,last);
    for(Re i=1;i<=T;++i){
    	scanf("%s",s+1),len[i]=strlen(s+1);Re last=1;
    	for(Re j=1;j<len[i];++j)last=SAM.insert(s[j]-'a',0,last);
    	Q[i].push_back(last=SAM.insert(s[len[i]]-'a',0,last));
    	for(Re j=1;j<len[i];++j)Q[i].push_back(last=SAM.insert(s[j]-'a',0,last));
	}
	SAM.build();
    for(Re i=1;i<=T;++i){
    	tmp[0]=ans=0;
    	for(Re j=0,SZ=Q[i].size();j<SZ;++j){
    		Re x=SAM.ask(Q[i][j],len[i]);
    		if(vis[x])continue;
    		tmp[++tmp[0]]=x,vis[x]=1,ans+=SAM.siz[x];
		}
		for(Re j=1;j<=tmp[0];++j)vis[tmp[j]]=0;
		printf("%lld\n",ans);
	}
}
Sevenk Love Oimaster 在线广义SAM 6.6.6 AC自动机与后缀数组
62 行
CPP JSON
【Sevenk Love Oimaster(在线广义SAM)】 字符串高级算法模板。 核心函数: void in(Re &x) — 核心算法函数 int insert(Re ch,Re last) — 插入元素 void updata(Re p,Re id) — 核心算法函数 void ask(char ch[]) — 核心算法函数 核心结构体:Suffix_Automaton 关键配置: N=2e5+5 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 61 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,Len[N];char s[N],ch[360003];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{
	int O,cnt[N],link[N],maxlen[N],trans[N][26];
	Suffix_Automaton(){O=1;}
	inline int insert(Re ch,Re last){
		if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];
		Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				if(maxlen[p]+1==maxlen[z]/*�����p==last*/)flag=1;
				y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[z]=link[x]=y;
			}
		}
		return flag?y:z;
	}
	int co[N];
	inline void updata(Re p,Re id){
		while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
	}
	inline void ask(char ch[]){
		Re p=1,flag=1;
		for(Re i=1;ch[i]&&flag;++i){
			Re a=ch[i]-'a';
			if(trans[p][a])p=trans[p][a];
			else flag=0;
		}
		printf("%d\n",flag?cnt[p]:0);
	}
}SAM;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i){
		scanf("%s",ch+1);Re last=1;
		for(Re j=1;ch[j];Len[i]=j,++j)last=SAM.insert(s[++t]=ch[j]-'a',last);
	}
	for(Re i=1,t=0;i<=n;++i)
		for(Re j=1,p=1;j<=Len[i];++j)
			SAM.updata(p=SAM.trans[p][s[++t]],i);
	while(T--)scanf("%s",ch+1),SAM.ask(ch);
}
Sevenk Love Oimaster 离线广义SAM 6.6.6 AC自动机与后缀数组
79 行
CPP JSON
【Sevenk Love Oimaster(离线广义SAM)】 字符串高级算法模板。 核心函数: void in(Re &x) — 核心算法函数 void insert(char ch[],Re id) — 插入元素 int insert(Re ch,Re last) — 插入元素 void updata(Re p,Re id) — 核心算法函数 void build(无参数) — 构建数据结构(建树/建图) void ask(char ch[]) — 核心算法函数 核心结构体:Trie, Suffix_Automaton 关键配置: N=2e5+5 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 78 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,Len[N];char s[N],ch[360003];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Trie{
	int O,c[N],fa[N],tr[N][26];
	Trie(){O=1;}
	inline void insert(char ch[],Re id){
		Re p=1;
		for(Re i=1;ch[i];Len[id]=i,++i){
			Re a=ch[i]-'a';s[++t]=a;
			if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
			p=tr[p][a];
		}
	}
}T1;
struct Suffix_Automaton{
	int O,pos[N],cnt[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
	Suffix_Automaton(){O=1;}
	inline int insert(Re ch,Re last){
		Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[z]=link[x]=y;
			}
		}
		return flag?y:z;
	}
	int co[N];
	inline void updata(Re p,Re id){
		while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
	}
	inline void build(){
		for(Re i=0;i<26;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);
		pos[1]=1;
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			pos[x]=insert(T1.c[x],pos[T1.fa[x]]);
			for(Re i=0;i<26;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
		}
		for(Re i=1,t=0;i<=n;++i)
			for(Re j=1,p=1;j<=Len[i];++j)
				updata(pos[p=T1.tr[p][s[++t]]],i);
	}
	inline void ask(char ch[]){
		Re p=1,flag=1;
		for(Re i=1;ch[i]&&flag;++i){
			Re a=ch[i]-'a';
			if(trans[p][a])p=trans[p][a];
			else flag=0;
		}
		printf("%d\n",flag?cnt[p]:0);
	}
}SAM;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch,i);
	SAM.build();
	while(T--)scanf("%s",ch+1),SAM.ask(ch);
}
58 行
CPP JSON
【AC自动机(Trie图)】 AC 自动机(Aho-Corasick Automaton)模板,多模式串匹配。 核心函数: void in(Re &x) — 核心算法函数 void insert(char ch[],Re id) — 插入元素 void get_fail(无参数) — 获取值 void sakura(char ch[]) — 后缀数组 核心结构体:AC_Automaton 关键配置: N=2e5+3 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+3;
int n;char ch[N*10];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct AC_Automaton{
	int O,edp[N],fail[N],tr[N][26];queue<int>Q;
	AC_Automaton(){O=1;}
	inline void insert(char ch[],Re id){
		Re p=1;
		for(Re i=1;ch[i];++i){
			Re a=ch[i]-'a';
			if(!tr[p][a])tr[p][a]=++O;
			p=tr[p][a];
		}
		edp[id]=p;
	}
	inline void get_fail(){
		for(Re i=0;i<26;++i)tr[0][i]=1;
		Q.push(1);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			for(Re i=0;i<26;++i)
				if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q.push(tr[x][i]);
				else tr[x][i]=tr[fail[x]][i];
		}
	}
	int ru[N],cnt[N];
	inline void sakura(char ch[]){
		for(Re i=1,p=1;ch[i];++i)p=tr[p][ch[i]-'a'],++cnt[p];
		for(Re i=2;i<=O;++i)++ru[fail[i]];
		for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			cnt[fail[x]]+=cnt[x];
			if(!(--ru[fail[x]]))Q.push(fail[x]);
		}
		for(Re i=1;i<=n;++i)printf("%d\n",cnt[edp[i]]);
	}
}AC;
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)scanf("%s",ch+1),AC.insert(ch,i);
	AC.get_fail();
	scanf("%s",ch+1);AC.sakura(ch);
}
LCT动态维护SAM Substring[Bzoj2555] 6.6.6 AC自动机与后缀数组
106 行
CPP JSON
【LCT动态维护SAM(Substring[Bzoj2555])】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 string In(Re mask) — 核心算法函数 void add(Re p,Re v) — 加法更新 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Suffix_Automaton, Link_Cut_Tree, QAQ 关键配置: N=12e5+3 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 105 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12e5+3;
int T,ans,mask;char op[10],s[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline string In(Re mask){
    scanf("%s",s);string chars=s;
    for(int j=0;j<chars.length();j++){
        mask=(mask*131+j)%chars.length();
        char t=chars[j];
        chars[j]=chars[mask];
        chars[mask]=t;
    }
    return chars;
}
struct Suffix_Automaton{
	struct Link_Cut_Tree{
		#define pl tr[p].ps[0]
		#define pr tr[p].ps[1]
		#define pf tr[p].fa
		int Q[N];
		struct QAQ{int fa,ans,add,ps[2];}tr[N];
		inline void add(Re p,Re v){tr[p].ans+=v,tr[p].add+=v;}
		inline void pushdown(Re p){
			Re v=tr[p].add;
			if(v){
				if(pl)add(pl,v);
				if(pr)add(pr,v);
				tr[p].add=0;
			}
		}
		inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
		inline int which(Re p){return tr[pf].ps[1]==p;}
		inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
		inline void rotate(Re p){
			Re fa=pf,fas=which(p);
			Re pa=tr[fa].fa,pas=which(fa);
			Re x=tr[p].ps[fas^1];
			if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
			connect(x,fa,fas),connect(fa,p,fas^1);
		}
		inline void splay(Re p){
			Re x=p,t=0;Q[++t]=x;
			while(nort(x))Q[++t]=x=tr[x].fa;
			while(t)pushdown(Q[t--]);
			for(Re fa;nort(p);rotate(p))
				if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
		}
		inline void access(Re p){for(Re son=0;p;son=p,p=pf)splay(p),pr=son;}
		inline void link(Re x,Re y){tr[x].fa=y,access(y),splay(y),add(y,tr[x].ans);}
		inline void cut(Re x){
			access(x),splay(x),add(tr[x].ps[0],-tr[x].ans);
			tr[tr[x].ps[0]].fa=0,tr[x].ps[0]=0;
		}
		inline int ask(Re x){splay(x);return tr[x].ans;}
	}LCT;
	int O,last,link[N],maxlen[N],trans[N][30];
	Suffix_Automaton(){last=O=1;}
	inline void insert(char ch){
		Re z=++O,p=last;LCT.tr[z].ans=1,maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1,LCT.link(z,1);
		else{
			Re x=trans[p][ch];
			if(maxlen[x]==maxlen[p]+1)link[z]=x,LCT.link(z,x);
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],LCT.cut(x),LCT.link(y,link[y]);
				link[x]=link[z]=y,LCT.link(x,y),LCT.link(z,y);
			}
		}
		last=z;
	}
	inline void add(string ch){
		for(Re i=0;ch[i];++i)insert(ch[i]-'A');
	}
	inline int ask(string ch){
		Re p=1;
		for(Re i=0;ch[i];++i)if(!(p=trans[p][ch[i]-'A']))return 0;
		return LCT.ask(p);
	}
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    in(T),scanf("%s",s+1);
    for(Re i=1;s[i];++i)SAM.insert(s[i]-'A');
	while(T--){
		scanf("%s",op);string s=In(mask);
		if(op[0]=='A')SAM.add(s);
		else mask^=(ans=SAM.ask(s)),printf("%d\n",ans);
	}
}
SAM后缀自动机 Suffix_Automaton 6.6.6 AC自动机与后缀数组
59 行
CPP JSON
【SAM后缀自动机】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 void insert(char ch) — 插入元素 void Tuopu(无参数) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:Suffix_Automaton 关键配置: N=2e6+5 说明:siz:һ���ȼ���ڵ�endpos��С�������ִ�����;freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 58 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5;
char ch[2000003];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{
	int O,last,ru[N],siz[N],link[N],maxlen[N],minlen[N],trans[N][26];queue<int>Q;
	Suffix_Automaton(){last=O=1;}
	inline void insert(char ch){
		Re z=++O,p=last;siz[z]=1,maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;//û�ҵ�trans[...][ch]
		else{
			Re x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x];
				
				link[z]=link[x]=y;
			}
		}
		last=z;
	}
	inline void Tuopu(){
		for(Re i=2;i<=O;++i)++ru[link[i]];
		for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			siz[link[x]]+=siz[x];
			if(!(--ru[link[x]]))Q.push(link[x]);
		}
	}
	inline void sakura(){
		for(Re i=2;i<=O;++i)minlen[i]=maxlen[link[i]]+1;
		Tuopu();Re ans=0;
		for(Re i=1;i<=O;++i)if(siz[i]>1)ans=max(ans,siz[i]*maxlen[i]);
		printf("%d\n",ans);
	}
}SAM;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s",ch+1);
	for(Re i=1;ch[i];++i)SAM.insert(ch[i]-'a');
	SAM.sakura();
}
SAM转后缀树 字母 letter 6.6.6 AC自动机与后缀数组
82 行
CPP JSON
【SAM转后缀树(字母 letter)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re ch,Re id) — 插入元素 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 LL calc(Re L,Re R) — 计算函数 void build(无参数) — 构建数据结构(建树/建图) char ask(LL K) — 核心算法函数 void sakura(无参数) — 后缀数组 核心结构体:Sakura2 关键配置: N=4e5+10 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 81 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4e5+10;
int n,x,y,T;LL P,M,G,K;char s[N>>1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Sakura2{
    int O,last,pos[N],siz[N],link[N],maxlen[N],trans[N][26];
    // siz[x]: 节点x的出现次数 (endpos的大小)
    inline void insert(Re ch,Re id){
        Re z=++O,p=last;pos[z]=id,siz[z]=1,maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1,pos[y]=pos[x];
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        last=z;
    }
    int t,ID[N],to[N][26];LL S[N];
    inline void dfs1(Re x){
        for(Re i=0;i<26;++i)
            if(to[x][i])dfs1(to[x][i]),siz[x]+=siz[to[x][i]];
    }
    inline void dfs2(Re x){
        if(x!=1)ID[++t]=x;
        for(Re i=0;i<26;++i)if(to[x][i])dfs2(to[x][i]);
    }
    inline LL calc(Re L,Re R){return 1ll*(L+R)*(R-L+1)/2;}
    inline void build(){
        last=O=1;
        for(Re i=1;i<=n/2;++i)swap(s[i],s[n-i+1]);
        for(Re i=1;i<=n;++i)insert(s[i]-'a',i);
        for(Re i=2;i<=O;++i)to[link[i]][s[pos[i]-maxlen[link[i]]]-'a']=i;
        dfs1(1),dfs2(1);
        for(Re i=1;i<=t;++i)x=ID[i],S[i]=S[i-1]+1ll*siz[x]*calc(maxlen[link[x]]+1,maxlen[x]);
    }
    inline char ask(LL K){
        Re l=1,r=t,x;
        while(l<r){
            Re mid=l+r>>1;
            if(S[mid]<K)l=mid+1;
            else r=mid;
        }
        x=ID[l],K-=S[l-1],l=maxlen[link[x]]+1,r=maxlen[x];
        while(l<r){
            Re mid=l+r>>1;
            if(1ll*siz[x]*calc(maxlen[link[x]]+1,mid)<K)l=mid+1;
            else r=mid;
        }
        K-=1ll*siz[x]*calc(maxlen[link[x]]+1,l-1),K=(K-1)%l+1;
        return s[pos[x]-K+1];
    }
    char ans;
    inline void sakura(){
        build();
        while(T--)scanf("%lld%lld",&P,&M),K=P*G%M+1,G+=(ans=ask(K)),putchar(ans),puts("");
    }
}T2;
int main(){
    freopen("letter.in","r",stdin);
    freopen("letter.out","w",stdout);
    scanf("%s",s+1),n=strlen(s+1);in(T);
    T2.sakura();
    fclose(stdin);
    fclose(stdout);
}
SAM转后缀树转后缀数组 不同子串个数 6.6.6 AC自动机与后缀数组
67 行
CPP JSON
【SAM转后缀树转后缀数组(不同子串个数)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 void get_height(无参数) — 获取值 void add(Re x,Re y,Re c) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void insert(Re ch,Re id) — 插入元素 void build(无参数) — 构建数据结构(建树/建图) 核心结构体:Suffix_Array, Suffix_Tree, Suffix_Automaton 关键配置: N=1e5+5 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 66 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+5;
int n;char s[N];LL ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Suffix_Array{
	int H[N],SA[N],rank[N],height[N];
	inline void get_height(){
		for(Re i=1;i<=n;++i)rank[SA[i]]=i;
		for(Re i=1,k=0;i<=n;++i){
			if(rank[i]==1)continue;
			if(k)--k;
			Re j=SA[rank[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
			height[rank[i]]=H[i]=k;
		}
	}
}SA;
int pan[N<<1],pos[N<<1];
struct Suffix_Tree{
	int t,tr[N<<1][26];
	inline void add(Re x,Re y,Re c){tr[x][c]=y;}
	inline void dfs(Re x){
		if(pan[x])SA.SA[++t]=pos[x];
		for(Re i=0;i<26;++i)if(tr[x][i])dfs(tr[x][i]);
	}
}ST;
struct Suffix_Automaton{
	int O,last,link[N<<1],maxlen[N<<1],trans[N<<1][26];
	Suffix_Automaton(){last=O=1;}
	inline void insert(Re ch,Re id){
		Re z=++O,p=last;maxlen[z]=maxlen[p]+1,pan[z]=1,pos[z]=id;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			Re x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				pos[y]=pos[x],link[y]=link[x],link[x]=link[z]=y;
			}
		}
		last=z;
	}
	inline void build(){
		for(Re i=n;i>=1;--i)insert(s[i]-'a',i);
		for(Re i=2;i<=O;++i)ST.add(link[i],i,s[pos[i]+maxlen[link[i]]]-'a');
	}
}SAM;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),scanf("%s",s+1),SAM.build(),ST.dfs(1),SA.get_height();
	for(Re i=1;i<=n;++i)ans+=n-SA.SA[i]+1-SA.height[i];
	printf("%lld\n",ans);
}
57 行
CPP JSON
【后缀数组(倍增)】 后缀数组(Suffix Array)模板(倍增法/DC3),排序所有后缀。 核心函数: void in(Re &x) — 核心算法函数 void get_SA(无参数) — 获取值 void get_Height(无参数) — 获取值 核心结构体:Suffix_Array 关键配置: N=1e6+3 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 56 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e6+3;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Array{
	int n,m,x[N],y[N],H[N],SA[N],cnt[N],rank[N],Height[N];char s[N];
	//Suf[i]: s[i,n]
	inline void get_SA(){
		m=128;
		for(Re i=1;i<=n;++i)++cnt[x[i]=s[i]];
		for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
		for(Re i=n;i>=1;--i)SA[cnt[x[i]]--]=i;
		for(Re len=1;len<=n;len<<=1){
			Re t=0;
			for(Re i=n-len+1;i<=n;++i)y[++t]=i;
			for(Re i=1;i<=n;++i)if(SA[i]>len)y[++t]=SA[i]-len;
			
			for(Re i=1;i<=m;++i)cnt[i]=0;
			for(Re i=1;i<=n;++i)++cnt[x[i]];
			for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
			for(Re i=n;i>=1;--i)SA[cnt[x[y[i]]]--]=y[i],y[i]=0;
			
			swap(x,y);
			x[SA[1]]=m=1;
			for(Re i=2;i<=n;++i)
				x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+len]==y[SA[i-1]+len])?m:++m;
			if(m==n)break;
		}
		for(Re i=1;i<=n;++i)printf("%d ",SA[i]);
	}
	inline void get_Height(){
		for(Re i=1;i<=n;++i)rank[SA[i]]=i;
		for(Re i=1,k=0;i<=n;++i){
			if(rank[i]==1)continue;
			if(k)--k;//H[i-1]-1<=H[i]
			Re j=SA[rank[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
			Height[rank[i]]=k;
		}
//		for(Re i=1;i<=n;++i)printf("%d ",Height[i]);
	}
}SA;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s",SA.s+1),SA.n=strlen(SA.s+1);
	SA.get_SA(),SA.get_Height();
}
回文自动机 回文树 6.6.6 AC自动机与后缀数组
43 行
CPP JSON
【回文自动机(回文树)】 回文自动机(Palindromic Tree)模板,存储所有回文子串。 核心函数: void in(Re &x) — 核心算法函数 int find(Re p,Re id) — 查找(并查集寻根/二分查找) void insert(Re ch,Re id) — 插入元素 void sakura(无参数) — 后缀数组 核心结构体:Palindromic_Automaton 关键配置: N=5e5+5 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 42 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+5;
char s[N];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Palindromic_Automaton{
	int O,last,siz[N],cnt[N],len[N],fail[N],trans[N][26];
	Palindromic_Automaton(){O=1,len[1]=-1,fail[0]=fail[1]=last=1;}
	// 0:偶数回文的根节点
	// 1:奇数回文的根节点
	inline int find(Re p,Re id){while(s[id-1-len[p]]!=s[id])p=fail[p];return p;}
	inline void insert(Re ch,Re id){
		Re cur=find(last,id),now=trans[cur][ch];
		if(!now){
			now=++O,len[now]=len[cur]+2;
			fail[now]=trans[find(fail[cur],id)][ch];
			cnt[now]=cnt[fail[now]]+1;
			trans[cur][ch]=now;
		}
		++siz[now],last=now;
	}
	inline void sakura(){
		for(Re i=O;i>=2;--i)siz[fail[i]]+=siz[i];
	}
}PAM;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s",s+1);
	for(Re i=1,k=0;s[i];++i){
		s[i]=(s[i]-'a'+k)%26+'a';
		PAM.insert(s[i]-'a',i);
		printf("%d ",k=PAM.cnt[PAM.last]);
	}
}
61 行
CPP JSON
【广义SAM(在线)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 Suffix_Automaton(无参数) — 核心算法函数 int insert(Re ch,Re last) — 插入元素 void sakura(无参数) — 后缀数组 核心结构体:Suffix_Automaton 关键配置: N=2e6+5 说明:link[i]: ��׺����;trans[i]: ״̬ת������;freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 60 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5;
int n;char ch[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{
    int O,link[N],maxlen[N],trans[N][26];
    //trans[i]: 状态转移指针
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last){
        if(trans[last][ch]){
            Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])return x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                return y;
            }
        }
        Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void sakura(){
        LL ans=0;
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i){
        scanf("%s",ch+1);Re last=1;
        for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last);
    }
    SAM.sakura();
}
68 行
CPP JSON
【广义SAM(离线bfs)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 Trie(无参数) — 核心算法函数 void insert(char ch[]) — 插入元素 Suffix_Automaton(无参数) — 核心算法函数 int insert(Re ch,Re last) — 插入元素 void build(无参数) — 构建数据结构(建树/建图) void sakura(无参数) — 后缀数组 核心结构体:Trie, Suffix_Automaton 关键配置: N=2e6+5,M=1e6+3 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 67 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Trie{
    int O,c[M],fa[M],tr[M][26];
    Trie(){O=1;}
    inline void insert(char ch[]){
        Re p=1;
        for(Re i=1;ch[i];++i){
            Re a=ch[i]-'a';
            if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
            p=tr[p][a];
        }
    }
}T1;
struct Suffix_Automaton{
    int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
    //trans[i]: 状态转移指针
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last){
        Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void build(){
        for(Re i=0;i<26;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);
        pos[1]=1;
        while(!Q.empty()){
            Re x=Q.front();Q.pop();
            pos[x]=insert(T1.c[x],pos[T1.fa[x]]);
            for(Re i=0;i<26;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
        }
    }
    inline void sakura(){
        LL ans=0;
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
    SAM.build(),SAM.sakura();
}
64 行
CPP JSON
【广义SAM(离线dfs)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 Trie(无参数) — 核心算法函数 void insert(char ch[]) — 插入元素 Suffix_Automaton(无参数) — 核心算法函数 int insert(Re ch,Re last) — 插入元素 void dfs(Re x) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) void sakura(无参数) — 后缀数组 核心结构体:Trie, Suffix_Automaton 关键配置: N=2e6+5,M=1e6+3 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 63 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Trie{
    int O,c[M],fa[M],tr[M][26];
    Trie(){O=1;}
    inline void insert(char ch[]){
        Re p=1;
        for(Re i=1;ch[i];++i){
            Re a=ch[i]-'a';
            if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
            p=tr[p][a];
        }
    }
}T1;
struct Suffix_Automaton{
    int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
    //trans[i]: 状态转移指针
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last){
        Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void dfs(Re x){
		for(Re i=0,to;i<26;++i)if(to=T1.tr[x][i])
			pos[to]=insert(T1.c[to],pos[x]),dfs(to);
	}
    inline void build(){pos[1]=1,dfs(1);}
    inline void sakura(){
        LL ans=0;
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
    SAM.build(),SAM.sakura();
}
广义SAM+线段树合并维护siz+倍增 Forensic Examination 6.6.6 AC自动机与后缀数组
122 行
CPP JSON
【广义SAM+线段树合并维护siz+倍增(Forensic Examination)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 QWQ max(QWQ A,QWQ B) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void change(Re &p,Re L,Re R,Re x) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 QWQ ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 Suffix_Automaton(无参数) — 核心算法函数 int insert(Re ch,Re last,Re id) — 插入元素 核心结构体:QWQ, Segment_Tree, QAQ, Suffix_Automaton, QAQ 关键配置: N=5e5+3,M=5e4+3,logN=21 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 121 行 CPP
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,M=5e4+3,logN=21;
int n,m,x,y,l,r,T,pos[N];char s[N],ch[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct QWQ{
    int x,id;QWQ(Re X=0,Re ID=0){x=X,id=ID;}
    inline bool operator>(const QWQ &O)const{return x!=O.x?x>O.x:id<O.id;}
};
inline QWQ max(QWQ A,QWQ B){return A>B?A:B;}
int pt[N+M<<1];
struct Segment_Tree{
    #define pl (tr[p].lp)
    #define pr (tr[p].rp)
    #define mid ((L+R)>>1)
    int O;
    struct QAQ{int lp,rp;QWQ ans;}tr[(M<<1)*30];
    inline void pushup(Re p){
        tr[p].ans=max(tr[pl].ans,tr[pr].ans);
    }
    inline void change(Re &p,Re L,Re R,Re x){
        if(!p)p=++O;
        if(L==R){++tr[p].ans.x,tr[p].ans.id=L;return;}
        if(x<=mid)change(pl,L,mid,x);
        else change(pr,mid+1,R,x);
        pushup(p);
    }
    inline int merge(Re p,Re q,Re L,Re R){
        if(!p||!q)return p+q;
        Re x=++O;
        if(L==R){tr[x]=tr[p],tr[x].ans.x+=tr[q].ans.x;return x;}
        tr[x].lp=merge(pl,tr[q].lp,L,mid);
        tr[x].rp=merge(pr,tr[q].rp,mid+1,R);
        pushup(x);return x;
    }
    inline QWQ ask(Re p,Re L,Re R,Re l,Re r){
        if(!p)return QWQ(0,m+1);
        if(l<=L&&R<=r)return tr[p].ans;
        QWQ ans=QWQ(0,m+1);
        if(l<=mid)ans=max(ans,ask(pl,L,mid,l,r));
        if(r>mid)ans=max(ans,ask(pr,mid+1,R,l,r));
        return ans;
    }
}TR;
struct Suffix_Automaton{
    int O,link[N+M<<1],maxlen[N+M<<1],trans[N+M<<1][26];
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last,Re id){
        if(trans[last][ch]){
            Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x]){if(id)TR.change(pt[x],1,m,id);return x;}
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                if(id)TR.change(pt[y],1,m,id);
                return y;
            }
        }
        Re z=++O,p=last;maxlen[z]=maxlen[p]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[x]==maxlen[p]+1)link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=link[z]=y;
            }
        }
        if(id)TR.change(pt[z],1,m,id);
        return z;
    }
    int o,deep[N+M<<1],head[N+M<<1],ant[N+M<<1][23];
    struct QAQ{int to,next;}a[N+M<<1];
    inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
    inline void dfs(Re x,Re fa){
        deep[x]=deep[ant[x][0]=fa]+1;
        for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
        for(Re i=head[x],to;i;i=a[i].next)
            dfs(to=a[i].to,x),pt[x]=TR.merge(pt[x],pt[to],1,m);
    }
    inline void build(){
        for(Re i=2;i<=O;++i)add(link[i],i);dfs(1,0);
    }
    inline int get(Re x,Re len){
        Re p=pos[x];
        for(Re i=logN;i>=0;--i)if(ant[p][i]&&maxlen[ant[p][i]]>=len)p=ant[p][i];
        return p;
    }
    inline void sakura(Re l,Re r,Re x,Re y){
        QWQ ans=TR.ask(pt[get(y,y-x+1)],1,m,l,r);
        if(ans.x==0)ans.id=l;
        printf("%d %d\n",ans.id,ans.x);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    scanf("%s",s+1),n=strlen(s+1),in(m);
    for(Re i=1;i<=m;++i){
        scanf("%s",ch+1);Re last=1;
        for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last,i);
    }
    for(Re i=1,last=1;i<=n;++i)pos[i]=last=SAM.insert(s[i]-'a',last,0);
    SAM.build(),in(T);
    while(T--)in(l),in(r),in(x),in(y),SAM.sakura(l,r,x,y);
}
区间本质不同子串个数 SAM+LCT+线段树 6.6.6 AC自动机与后缀数组
117 行
CPP JSON
【区间本质不同子串个数(SAM+LCT+线段树)】 字符串高级算法模板。 核心函数: void in(Re &x) — 核心算法函数 void updata(Re p,Re L,Re R,LL v) — 核心算法函数 void pushdown(Re p,Re L,Re R) — 下传懒标记 void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void insert(Re ch,Re id) — 插入元素 void updata(Re p,Re v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 核心结构体:Query, Segment_Tree, QAQ, Suffix_Automaton, Link_Cut_Tree 关键配置: N=1e5+3,M=2e5+3 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 116 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=2e5+3;
int n,T;LL Ans[M];char s[N];
struct Query{int l,r,id;inline bool operator<(const Query &O)const{return r<O.r;}}Q[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	struct QAQ{LL S,add;}tr[N<<2];
	inline void updata(Re p,Re L,Re R,LL v){tr[p].add+=v,tr[p].S+=v*(R-L+1);}
	inline void pushdown(Re p,Re L,Re R){
		if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
		if(l<=L&&R<=r){updata(p,L,R,v);return;}
		pushdown(p,L,R);
		if(l<=mid)change(pl,L,mid,l,r,v);
		if(r>mid)change(pr,mid+1,R,l,r,v);
		tr[p].S=tr[pl].S+tr[pr].S;
	}
	inline LL ask(Re p,Re L,Re R,Re l,Re r){
		if(l<=L&&R<=r)return tr[p].S;
		pushdown(p,L,R);LL ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
	#undef pl
	#undef pr
}TR;
struct Suffix_Automaton{
	int O,last,pos[N],link[N<<1],maxlen[N<<1],trans[N<<1][26];
	Suffix_Automaton(){last=O=1;}
	inline void insert(Re ch,Re id){
		Re z=++O,p=last;maxlen[z]=maxlen[p]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			Re x=trans[p][ch];
			if(maxlen[x]==maxlen[p]+1)link[z]=x;
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[z]=link[x]=y;
			}
		}
		pos[id]=last=z;
	}
}SAM;
struct Link_Cut_Tree{
	#define pl (tr[p].ps[0])
	#define pr (tr[p].ps[1])
	#define pf (tr[p].fa)
	#define pv (tr[p].v)
	int Q[N<<1];
	struct QAQ{int v,fa,tag,ps[2];}tr[N<<1];
	inline void updata(Re p,Re v){tr[p].tag=tr[p].v=v;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl,tr[p].tag);
			if(pr)updata(pr,tr[p].tag);
			tr[p].tag=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(tr[x].fa)Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p,Re r){
		Re son=0;
		for(;p;son=p,p=pf){
			splay(p);
			if(pv)TR.change(1,1,n,pv-SAM.maxlen[p]+1,pv-SAM.maxlen[pf],-1);
			pr=son;
		}
		updata(son,r),TR.change(1,1,n,1,r,1);
	}
}T1;
int main(){
//    freopen("123.txt","r",stdin);
    scanf("%s",s+1),n=strlen(s+1),in(T);
	for(Re i=1;i<=n;++i)SAM.insert(s[i]-'a',i);
	for(Re i=2;i<=SAM.O;++i)T1.tr[i].fa=SAM.link[i];
	for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
    sort(Q+1,Q+T+1);
    for(Re i=1,r=0;i<=T;++i){
    	while(r<Q[i].r)++r,T1.access(SAM.pos[r],r);
    	Ans[Q[i].id]=TR.ask(1,1,n,Q[i].l,Q[i].r);
	}
	for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
喵星球上的点名 广义SAM 6.6.6 AC自动机与后缀数组
86 行
CPP JSON
【喵星球上的点名(广义SAM)】 字符串高级算法模板。 核心函数: void in(Re &x) — 核心算法函数 int insert(Re ch,Re last) — 插入元素 void updata(Re p,Re id) — 核心算法函数 void updata_(Re p,Re id) — 核心算法函数 void ask(Re ch[],Re L) — 核心算法函数 核心结构体:Suffix_Automaton 关键配置: N=2e5+5 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 85 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,x,s[N],ch[N],Len[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{	
	int O,pos[N],cnt[N],link[N],maxlen[N],minlen[N];queue<int>Q;map<int,int>trans[N];
	Suffix_Automaton(){O=1;}
	inline int insert(Re ch,Re last){
		if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];
		Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				if(maxlen[p]+1==maxlen[z])flag=1;
				y=++O;maxlen[y]=maxlen[p]+1;
				trans[y]=trans[x];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[z]=link[x]=y;
			}
		}
		return flag?y:z;
	}
	int co[N];
	inline void updata(Re p,Re id){
		while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
	}
	int gs[N],Ans[N];
	inline void updata_(Re p,Re id){
		while(p&&co[p]!=id)Ans[id]+=gs[p],co[p]=id,p=link[p];
	}
	inline void ask(Re ch[],Re L){
		Re p=1,flag=1;
		for(Re i=1;i<=L&&flag;++i){
			Re a=ch[i];
			if(trans[p][a])p=trans[p][a];
			else flag=0;
		}
		if(flag)++gs[p];
		printf("%d\n",flag?cnt[p]:0);
	}
}SAM;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i){
		in(Len[(i<<1)-1]);Re last=1;
		for(Re j=1;j<=Len[(i<<1)-1];++j)in(x),last=SAM.insert(s[++t]=x,last);
		in(Len[i<<1]);last=1;
		for(Re j=1;j<=Len[i<<1];++j)in(x),last=SAM.insert(s[++t]=x,last);
	}
	for(Re i=1,t=0;i<=n;++i){
		for(Re j=1,p=1;j<=Len[(i<<1)-1];++j)
			SAM.updata(p=SAM.trans[p][s[++t]],i);
		for(Re j=1,p=1;j<=Len[i<<1];++j)
			SAM.updata(p=SAM.trans[p][s[++t]],i);
	}
	while(T--){
		in(Len[0]);
		for(Re i=1;i<=Len[0];++i)in(ch[i]);
		SAM.ask(ch,Len[0]);
	}
	memset(SAM.co,0,sizeof(SAM.co));
	for(Re i=1,t=0;i<=n;++i){
		for(Re j=1,p=1;j<=Len[(i<<1)-1];++j)
			SAM.updata_(p=SAM.trans[p][s[++t]],i);
		for(Re j=1,p=1;j<=Len[i<<1];++j)
			SAM.updata_(p=SAM.trans[p][s[++t]],i);
	}
	for(Re i=1;i<=n;++i)printf("%d ",SAM.Ans[i]);
}
回文串 Manacher+SAM+倍增 6.6.6 AC自动机与后缀数组
73 行
CPP JSON
【回文串(Manacher+SAM+倍增)】 回文自动机(Palindromic Tree)模板,存储所有回文子串。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re ch) — 插入元素 void add(Re x,Re y) — 加法更新 void dfs(Re x,Re fa) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) void check(Re x,Re len) — 判定/检查函数 void sakura(无参数) — 后缀数组 核心结构体:Suffix_Automaton, QAQ 关键配置: N=6e5+5,logN=19 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6e5+5,logN=19;
char s[N>>1];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Suffix_Automaton{
	int O,last,pos[N],siz[N],link[N],maxlen[N],trans[N][26];LL ans;
	Suffix_Automaton(){last=O=1;}
	inline void insert(Re ch){
		Re z=++O,p=last;siz[z]=1,maxlen[z]=maxlen[last]+1;
		while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
		if(!p)link[z]=1;
		else{
			Re x=trans[p][ch];
			if(maxlen[p]+1==maxlen[x])link[z]=x;
			else{
				Re y=++O;maxlen[y]=maxlen[p]+1;
				for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
				while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
				link[y]=link[x],link[x]=link[z]=y;
			}
		}
		last=z;
	}
	int o,deep[N],head[N],ant[N][20];
	struct QAQ{int to,next;}a[N];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1];
		for(Re i=head[x];i;i=a[i].next)dfs(a[i].to,x),siz[x]+=siz[a[i].to];
	}
	inline void build(){
		for(Re i=1;s[i];++i)insert(s[i]-'a'),pos[i]=last;
		for(Re i=2;i<=O;++i)add(link[i],i);
		dfs(1,0);
	}
	inline void check(Re x,Re len){
		Re p=pos[x+len-1];
		for(Re i=logN;i>=0;--i)
			if(maxlen[ant[p][i]]>=len)p=ant[p][i];
		ans=max(ans,(LL)len*siz[p]);
	}
	int m,r[N];char b[N];
	inline void sakura(){
		build();
		b[m=0]='$',b[++m]='|';
		for(Re i=1;s[i];++i)b[++m]=s[i],b[++m]='|';
		for(Re i=1,R=0,mid=0;i<=m;++i){
			r[i]=i<=R?min(r[(mid<<1)-i],R-i+1):1;
			while(b[i-r[i]]==b[i+r[i]]){
				++r[i];
				if(i+r[i]-1>R)check(i-r[i]+1+1>>1,r[i]-!(i+r[i]&1));
			}
			if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
		}
		printf("%lld\n",ans);
	}
}SAM;
int main(){
	freopen("123.txt","r",stdin);
	scanf("%s",s+1),SAM.sakura();
}
40 行
CPP JSON
【回文串(PAM)】 回文自动机(Palindromic Tree)模板,存储所有回文子串。 核心函数: void in(Re &x) — 核心算法函数 int find(Re p,Re id) — 查找(并查集寻根/二分查找) void insert(Re ch,Re id) — 插入元素 void sakura(无参数) — 后缀数组 核心结构体:Palindromic_Automaton 关键配置: N=3e5+5 说明:freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5;
char s[N];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Palindromic_Automaton{
	int O,last,siz[N],len[N],fail[N],trans[N][26];
	Palindromic_Automaton(){O=1,len[1]=-1,fail[0]=fail[1]=last=1;}
	inline int find(Re p,Re id){while(s[id-1-len[p]]!=s[id])p=fail[p];return p;}
	inline void insert(Re ch,Re id){
		Re cur=find(last,id),now=trans[cur][ch];
		if(!now){
			now=++O,len[now]=len[cur]+2;
			fail[now]=trans[find(fail[cur],id)][ch];
			trans[cur][ch]=now;
		}
		++siz[now],last=now;
	}
	inline void sakura(){
		LL ans=0;
		for(Re i=O;i>=2;--i)siz[fail[i]]+=siz[i],ans=max(ans,(LL)siz[i]*len[i]);
		printf("%lld\n",ans);
	}
}PAM;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s",s+1);
	for(Re i=1;s[i];++i)PAM.insert(s[i]-'a',i);
	PAM.sakura();
}
找相同子串 (广义SAM记录siz) 在线 6.6.6 AC自动机与后缀数组
69 行
CPP JSON
【找相同子串 (广义SAM记录siz)(在线)】 后缀自动机(Suffix Automaton)模板,压缩存储所有子串。 核心函数: void in(Re &x) — 核心算法函数 Suffix_Automaton(无参数) — 核心算法函数 int insert(Re ch,Re last,Re id) — 插入元素 void sakura(无参数) — 后缀数组 核心结构体:Suffix_Automaton 关键配置: N=8e5+5 说明:siz[x]: |endpos[x]| ���ڵ�x��endpos��С;freopen("123.txt","r",stdin); 适用场景:最长公共子串、不同子串计数、字符串周期分析
C++ 68 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=8e5+5;
char ch[200003];LL ans;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{
    int O,ru[N],link[N],maxlen[N],siz[N][2],trans[N][26];queue<int>Q;
    // siz[x]: |endpos[x]| 节点x的endpos大小
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last,Re id){
        if(trans[last][ch]){
            Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x]){siz[x][id]=1;return x;} 
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                siz[y][id]=1;return y;
            }
        }
        Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        siz[z][id]=1;
        return z;
    }
    inline void sakura(){
        for(Re i=2;i<=O;++i)++ru[link[i]];
        for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
        while(!Q.empty()){
            Re x=Q.front();Q.pop();
            siz[link[x]][0]+=siz[x][0];
            siz[link[x]][1]+=siz[x][1];
            if(!(--ru[link[x]]))Q.push(link[x]);
        }
        for(Re i=2;i<=O;++i)//ͳ�ƴ�
            ans+=(LL)siz[i][0]*siz[i][1]*(maxlen[i]-maxlen[link[i]]);
        printf("%lld\n",ans);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    for(Re i=0;i<2;++i){
        scanf("%s",ch+1);Re last=1;
        for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last,i);
    }
    SAM.sakura();
}
已复制