设查询的字符串为A和B，B接到A前面（中间用不在字符集内的字符隔开），求next数组的最后一项。因为next[i] = 同时是字串0~i的前缀/后缀的最长字串的长度。
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<string> #include<map> using namespace std; typedef long long ll; int N; map< int , string >mmp; int Q; int l,r; int lps[300005]; map< pair< int , int > , int >res; int min2(int a,int b){return a<b?a:b;} void initlps(string x){ lps[0]=lps[1]=0; int len = x.length(); for(int i=1;i<len;i++){ int j = lps[i]; while(j&&x[i]!=x[j]){ j = lps[j]; } lps[i+1] = (x[i]==x[j])? j+1: 0; } } int chk(int l,int r){ string t = mmp[r] + "$" + mmp[l]; initlps(t); /* cout<<t<<endl; cout<<"-> "; for(int i=0;i<=t.length();i++){ cout<<lps[i]<<" "; } cout<<endl; */ int lenr = mmp[r].length(); lenr++; int lenl = mmp[l].length(); return min2(lps[lenl+lenr], min2(lenr-1, lenl)); } int main(){ ios::sync_with_stdio(false); cin>>N; for(int i=0;i<N;i++){ string x; cin>>x; mmp[i+1]=x; } cin>>Q; for(int i=0;i<Q;i++){ cin>>l>>r; cout<<chk(l,r)<<endl; } return 0; }