题意： n个串，每次查询两个，问最长的公共自串并且这个子串要是n个串其中一个的前缀。

思路：正解是AC自动机。。。这里瞎搞了一下居然过了，直接二分答案，然后判断（类似hash求公共子串一样），就再加一个是不是前缀的判断就好。。

时间复杂度理论上最差n*m*logn。。。但是神奇的只跑了150ms。。。

代码：

#include
    
     using namespace std;#define MEM(a,b) memset(a,b,sizeof(a))#define bug puts("bug");#define PB push_back#define MP make_pair#define X first#define Y secondtypedef unsigned long long ll;typedef pair
     
       pii;const int maxn=1e5+10;const int mod=1e9+7;using namespace std;int t,m,n,k;string s[maxn];const unsigned long long SEED = 13331;unsigned long long P[maxn],S[maxn];unsigned long long HS(int l,int r,int x){    if(l==r) return s[x][l-1];    return S[r] - S[l-1]*P[r-l+1];}unordered_set
      
        st,tmp;bool ok(int len,int x,int y){    tmp.clear();    for(int i=1;i<=s[x].size();i++)        S[i] = S[i-1]*SEED + s[x][i-1];    for(int i=1;i+len-1<=s[x].size();i++)        tmp.insert(HS(i,i+len-1,x));    for(int i=1;i<=s[y].size();i++)        S[i] = S[i-1]*SEED + s[y][i-1];    for(int i=1;i+len-1<=s[y].size();i++)        if(tmp.count(HS(i,i+len-1,y))&&st.count(HS(i,i+len-1,y)))            return true;    return false;}int main(){    P[0] = 1;S[0]=0;    for(int i = 1; i < maxn; i++)P[i] = P[i-1] * SEED;    ios::sync_with_stdio(false);    cin>>t;    while(t--){        st.clear();        cin>>n;        for(int i=0;i
       
        >s[i];        for(int i=0;i
        
         >m;        int x,y;        for(int i=0;i
         
          >x>>y; --x;--y; int l=0,r=min(s[x].size(),s[y].size()); while(l<=r){ int mid=(l+r)/2; if(ok(mid,x,y)) l=mid+1; else r=mid-1; } cout<
          
           <