首页 > 代码库 > hdu 4622

hdu 4622

2024-11-02 08:49:01   209人阅读

Problem Description

Now you are back,and have a task to do:
Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.
And you have some query,each time you should calculate f(s[l...r]), s[l...r] means the sub-string of s start from l end at r.
 

 

Input

The first line contains integer T(1<=T<=5), denote the number of the test cases.
For each test cases,the first line contains a string s(1 <= length of s <= 2000).
Denote the length of s by n.
The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.
 

 

Output

For each test cases,for each query,print the answer in one line.
 

 

Sample Input

2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5
 

Sample Output

3
1
7
5
8
1
3
8
5
1
 
题意:
给出一个字符串,求出在每个区间内的字串的个数....
 
思路:
两个做法,SAM 和 SA.
先说SAM. SAM的一个非常实用的性质,SAM是在线增量构造的.所以,我们就能够在线构造每个区间所对应的SAM.
合并左端点相同的询问,然后在线构造SAM,构造出SAM后,用O(n)的时间内统计出字串就ok了. 跟SPOJ那道题方法差不多.
 
然后是SA
参考的沐阳的博客....写得非常有道理.
构造出SA之后,我们通过遍历在局部的后缀(起点在[L,R]之间)来计算字串的贡献.....
关键是我们如何通过全局的SA来推算局部的SA.
la 与 lb 分别为一前一后的后缀在区间内的长度.
 
如果 lcp < la && lcp < lb
那么 la 就是下一个后缀.
 
如果 lcp >= la && lcp >= lb
如果 la < lb 就要换后缀.
 
如果 lcp >= la &&　lcp < lb
就更换后缀．
 
这样下来我们就能够得出全局的SA
然后在中间维护一个rmq就能够快速求出lcp
问题就解决了.
 
技术分享
 1 #include<cstdlib> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define rep(i,a,b) for(i = a; i < b; ++i) 6 #define rev(i,a,b) for(i = a; i >= b; --i) 7 using namespace std; 8 const int maxn = (int)2500, inf = 0x3f3f3f3f; 9 int sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],c[maxn];10 char str[maxn];11 int n;12 int cmp(int x[],int a,int b,int c){13     return x[a] == x[b] && x[a+c] == x[b+c];14 }15 void build(int m){16     int i,j,p = 0, *x = t1, *y = t2;17     rep(i,0,m) c[i] = 0;18     rep(i,0,n) c[x[i] = str[i]]++;19     rep(i,1,m) c[i] += c[i-1];20     rev(i,n-1,0) sa[--c[x[i]]] = i;21     for(j = 1; j < n && p < n; j <<= 1, m = p){22         p = 0;23         rep(i,n-j,n) y[p++] = i;24         rep(i,0,n) if(sa[i] >= j) y[p++] = sa[i] - j;25         rep(i,0,m) c[i] = 0;26         rep(i,0,n) c[x[y[i]]]++;27         rep(i,1,m) c[i] += c[i-1];28         rev(i,n-1,0) sa[--c[x[y[i]]]] = y[i];29         for(swap(x,y), p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)30             x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p - 1 : p++;31     }32 }33 void calc_height(){34     int i,j,k = 0;35     rep(i,0,n) rank[sa[i]] = i;36     for(i = 0; i < n; height[rank[i++]] = k)37         for(k ? k-- : 0, j = sa[rank[i] - 1]; str[i+k] == str[j+k] && min(i,j) + k < n; k++);38 }39 int l,r,lcp,last,ret;40 int getlen(int st,int ed){41     return ed - st + 1;42 }43 int calc(int now,int pas){44     int la = getlen(sa[now],r), lb = getlen(sa[pas],r);    45     return pas ? la - min(lcp,min(lb,la)) : la;46 }47 int getnext(int now,int pas){48     if(!pas) return now;49     int la = getlen(sa[now],r), lb = getlen(sa[pas],r);50     if(lcp < min(la,lb)) return now;51     if(lcp >= la && lcp >= lb && la > lb) return now;52     if(lcp < la && lcp >= lb) return now;53     return pas;54 }55 void solve(){56     int i;57     ret = last = 0; lcp = inf;58     rep(i,0,n){59         if(l <= sa[i] && sa[i] <= r){60             if(last) lcp = min(lcp,height[i]);61             ret += calc(i,last);62             int t = getnext(i,last);63             if(t == i) lcp = getlen(sa[i],r), last = i;64         }65         else if(last) lcp = min(lcp, height[i]);66     }67     printf("%d\n",ret);68 }69 int main()70 {71     freopen("rec.in","r",stdin);72     freopen("rec.out","w",stdout);73     int T,q;74     scanf("%d\n",&T);75     while(T--){76         scanf("%s",str);77         n = strlen(str);78         str[n++] = ‘a‘ - 1;79         build(255);80         calc_height();81         scanf("%d\n",&q);82         while(q--){83             scanf("%d %d\n",&l,&r);84             l--; r--;85             solve();86         }87     }88     return 0;89 }
View Code

 

hdu 4622


联系
我们