UVA 12338 - Anti-Rhyme Pairs(後綴數組+RMQ)

UVA 12338 - Anti-Rhyme Pairs

題目鏈接

題意：給定一些字符串，每次詢問求出兩個字符串的最長公共前綴的長度

思路：把字符串排序，就能求出height和rank數組，然後利用RMQ查詢即可

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100005;

typedef pair pii;

pii str[N];
int save[N];

int t, n, height[N], rank[N];

void init() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
	cin >> str[i].first;
	save[i] = str[i].first.length();
	str[i].second = i;
    }
    sort(str, str + n);
    for (int i = 0; i < n; i++) {
	rank[str[i].second] = i;
	if (i == 0) continue;
	int len = min(str[i - 1].first.length(), str[i].first.length());
	int j;
	for (j = 0; j < len; j++) {
	    if (str[i - 1].first[j] != str[i].first[j])
		break;
	}
	height[i] = j;
    }
}

int best[N * 10][20];

void initRMQ() {
    for (int i = 0; i < n; i++) best[i][0] = height[i];
    for (int j = 1; (1< R) swap(L, R);
    L++;
    int k = 0;
    while ((1<<(k + 1)) <= R - L + 1) k++;
    return min(best[L][k], best[R - (1<