欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51nod 1732 51nod婚姻介绍所 后缀数组 + rmq

程序员文章站 2022-03-03 07:59:53
...

传送门:51nod1732

题意:中文题。

思路:看完就感觉是后缀数组,翻了翻白书,果然是模板题,套个rmq就好了。

我从网上扒了个后缀数组的模板然后自己写了个线段树实现rmq,其实直接套kuangbin巨巨的模板就好,连带rmq什么都是全的。

代码:

#include <stdio.h>
#include<bits/stdc++.h> 
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define rep(i,n) for(int i = 0;i < n; i++)  
using namespace std;  
const int size  = 200005,INF = 1<<30;  
int rk[size],sa[size],height[size],w[size],wa[size],res[size];  
void getSa (int len,int up) {  
    int *k = rk,*id = height,*r = res, *cnt = wa;  
    rep(i,up) cnt[i] = 0;  
    rep(i,len) cnt[k[i] = w[i]]++;  
    rep(i,up) cnt[i+1] += cnt[i];  
    for(int i = len - 1; i >= 0; i--) {  
        sa[--cnt[k[i]]] = i;  
    }  
    int d = 1,p = 0;  
    while(p < len){  
        for(int i = len - d; i < len; i++) id[p++] = i;  
        rep(i,len)  if(sa[i] >= d) id[p++] = sa[i] - d;  
        rep(i,len) r[i] = k[id[i]];  
        rep(i,up) cnt[i] = 0;  
        rep(i,len) cnt[r[i]]++;  
        rep(i,up) cnt[i+1] += cnt[i];  
        for(int i = len - 1; i >= 0; i--) {  
            sa[--cnt[r[i]]] = id[i];  
        }   
        swap(k,r);  
        p = 0;  
        k[sa[0]] = p++;  
        rep(i,len-1) {  
            if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d])  
                k[sa[i+1]] = p - 1;  
            else k[sa[i+1]] = p++;  
        }  
        if(p >= len) return ;  
        d *= 2,up = p, p = 0;  
    }  
}  
void getHeight(int len) {  
    rep(i,len) rk[sa[i]] = i;  
    height[0] =  0;  
    for(int i = 0,p = 0; i < len - 1; i++) {  
        int j = sa[rk[i]-1];  
        while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) {  
            p++;  
        }  
        height[rk[i]] = p;
        p = max(0,p - 1);  
    }  
}  
int getSuffix(char s[]) {  
    int len = strlen(s),up = 0;   
    for(int i = 0; i < len; i++) {  
        w[i] = s[i];  
        up = max(up,w[i]);  
    }  
    w[len++] = 0;  
    getSa(len,up+1);  
    getHeight(len);  
    return len;  
}
int rmq[size], cnt;
void build(int l, int r, int rt)
{
	if(l == r)
	{
		rmq[rt] = height[cnt++];
		return ;
	}
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
	rmq[rt] = min(rmq[rt << 1], rmq[rt << 1 | 1]); 
}
int query(int L, int R, int l, int r, int rt)
{
	if(L <= l && r <= R)
	return rmq[rt];
	int mid = (l + r) >> 1;
	int ans = INF;
	if(L <= mid)
	ans = min(ans, query(L, R, lson));
	if(R > mid)
	ans = min(ans, query(L, R, rson));
	return ans;
}
char s[1100];
int main()
{
	int n, q, l, r;
	cin >> n;
	cin >> s;
	getSuffix(s);
	build(1, n, 1);
	cin >> q;
	while(q--)
	{
		scanf("%d %d", &l, &r);
		if(l == r)
		{
			printf("%d\n", n - l);
			continue;
		}
		l = rk[l];
		r = rk[r];
		if(l > r) swap(l, r);
		l++;//注意rmq的区间
		printf("%d\n", query(l + 1, r + 1, 1, n, 1));//注意建树是1--n的范围,l和r是0--n-1的范围 
	}
}