3999:The longest constant gene

文字列がいくつか与えられるので全ての文字列に現れる部分文字列の中で最長のものの長さを求めよ。

suffix arrayを使えば良い。共通部分文字列は蟻本に詳しく書いてる。

嘘解法だった。隣同士の最長共通部分文字列しか計算してないのに通っていた。

#define INF (1<<29)

using namespace std;
 
const int MAX_L = 7*(1e+6);
string S,T;
int sa[MAX_L], lcp[MAX_L];
int rank[MAX_L];
int tmp[MAX_L];
int k;
int ret;

int solve(){
  int sl = S.length();
  S += '$' + T;
  
  construct_sa(S,sa);
  construct_lcp(S,sa,lcp);
  
  int ans = 0;
  for(int i=0; i<S.size(); i++){
    if((sa[i] < sl) != (sa[i+1] < sl)){
      ans = max(ans,lcp[i]);
    }
  }
  return ans;
}

int longestCommonSubsequence(vector<string>strs){
  int n=strs.size();
    ret = INF;
    for(int i=0;i<n-1;i++){
      S = strs[i];
      T = strs[i+1];
      ret = min(ret,solve());
    }
    return ret;
}

int main(void){
  int tc;
  cin >> tc;
  while(tc--){
    
    for(int i=0; i<MAX_L; i++)
      tmp[i] = rank[i] = sa[i] = lcp[i] = 0;
    
    int n;
    cin >> n;
    vector<string>strs(n);
    for(int i=0; i<n; i++)cin >> strs[i];
    
    cout << longestCommonSubsequence(strs) << endl;
  }
  return 0;
}