uva 12338 - Anti-Rhyme Pairs(后缀数组+RMQ)

题目链接：uva 12338 - Anti-Rhyme Pairs

题目大意：给定若干个字符串，每次询问两个字符串的最长公共前缀。

解题思路：本来应该将每个字符串连接起来做后缀数组，但其实可以直接把一个字符串看成是一个字符，然后排序了就对应是SA数组，然后处理height即可。然后根据后缀数组的性质，字符串i和j的最长公共前缀长度即为rank[i]+1~rank[j]之间height的最小值。特判i=j的情况。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; typedef pair
         
           pii; const int maxn = 1e5+5; int Rank[maxn]; int dp[maxn][20]; vector
          
            g; vector
           
             height; void rmq_init(const vector
            
             & A) { int n = A.size(); for (int i = 0; i < n; i++) dp[i][0] = A[i]; for (int j = 1; (1<
             
               r) swap(l, r); l++; int k = 0; while ((1<<(k+1)) <= r - l + 1) k++; return min(dp[l][k], dp[r - (1<
              
               > cas; for (int kcas = 1; kcas <= cas; kcas++) { cin >> n; g.clear(); for (int i = 0; i < n; i++) { cin >> s; g.push_back(make_pair(s, i)); } solve(); cout << "Case " << kcas << ":" << endl; cin >> n; while (n--) { cin >> l >> r; cout << rmq_query(Rank[l-1], Rank[r-1]) << endl; } } return 0; }