首页 > 代码库 > hdu 4622
hdu 4622
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.
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.
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 }
hdu 4622
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。