题意：
求两个字符串的最长公共后缀，使得该后缀是某个字符串的前缀。
题解：
直接利用 $fail$ 指针的定义即可。
相当于求自动机上两点的 LCA，好像倍增可以，怕炸空间就老老实实写树剖吧。
Code:
#include #include #include #include #include #include #define idx str[i]-'a'#define maxn 2000103#define root 1#define sigma 27#define mod 1000000007 #define ll long long using namespace std;void setIO(string a){ freopen((a+".in").c_str(),"r",stdin); } char arr[maxn];int ch[maxn<<1][sigma],pos[maxn<<1],fail[maxn<<1],nodes=1, p[maxn];int hash[maxn<<1],cnt;void insert(char str[],int id){ int n=strlen(str); int j=root; for(int i=0;i
Q;int dep[maxn], f[23][maxn];void getfail(){ dep[root]=0; for(int i=0;i
dep[b]) swap(a,b); if(dep[a]!=dep[b]) for(int i=22;i>=0;--i) if(dep[f[i][b]]>=dep[a]) b=f[i][b]; if(a==b) return hash[a]; for(int i=22;i>=0;--i) if(f[i][a]!=f[i][b]) a=f[i][a],b=f[i][b]; return hash[f[0][a]];}int main(){ //setIO("input"); int n; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",arr),insert(arr,i); p[i]=strlen(arr); p[i]+=p[i-1]; } getfail(); int m; scanf("%d",&m); for(int cas=1;cas<=m;++cas){ int i,j,k,l; scanf("%d%d%d%d",&i,&j,&k,&l); int y=query(pos[p[k-1]+l],pos[p[i-1]+j]); printf("%d\n",y); } return 0;}