1314 – Names for Babies PDF (English) Statistics Forum Time Limit: 4 second(s)Memory Limit: 32 MB
Long time ago, there was a strange kingdom. Peoples of different religions, different cultures used to live there. But as they were different, their names were also different. So, in schools, offices, it was quite tough to call someone using his/her name, because some names were too hard to be pronounced by persons from different culture.
So, the king made a plan. He took a string S and two integers p and q and made a rule that names of the babies should be a substring of S, and the length should be between p and q (inclusive).
Now you are given S, p and q you have to find the number of distinct names that can be made. Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing a string S. The length of S will be between 2 and 10000 (inclusive) and S contains lowercase English letters only. The next line contains two integer p and q (1 ≤ p ≤ q ≤ length(S)). Output
For each case, print the case number and the number of distinct names that can be made. Sample Input
Output for Sample Input
1
abcdef
2 5
Case 1: 14 Note
This problem was used in contest 12. But the length of S was between 2 and 100.
明显 后缀数组题，统计不同的子串，只不过统计的时候，只统计那些长度在要求的范围内的串
/*************************************************************************> File Name: LightOJ1314.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月09日 星期四 19时52分15秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;char str[12000];class SuffixArray{public:N = 12000;int init[N];int X[N];int Y[N];int Rank[N];int sa[N];int height[N];int buc[N];int LOG[N];int dp[N][20];int size;void clear(){size = 0;}void insert(int n){init[size++] = n;}bool cmp(int *r, int a, int b, int l){return (r[a] == r[b] && r[a + l] == r[b + l]);}void getsa(int m = 256) //m一般为最大值+1{init[size] = 0;int l, p, *x = X, *y = Y, n = size + 1;for (int i = 0; i < m; ++i){buc[i] = 0;}for (int i = 0; i < n; ++i){++buc[x[i] = init[i]];}for (int i = 1; i < m; ++i){buc[i] += buc[i – 1];}for (int i = n – 1; i >= 0; –i){sa[–buc[x[i]]] = i;}for (l = 1, p = 1; l <= n && p < n; m = p, l *= 2){p = 0;for (int i = n – l; i < n; ++i){y[p++] = i;}for (int i = 0; i < n; ++i){if (sa[i] >= l){y[p++] = sa[i] – l;}}for (int i = 0; i < m; ++i){buc[i] = 0;}for (int i = 0; i < n; ++i){++buc[x[y[i]]];}for (int i = 1; i < m; ++i){buc[i] += buc[i – 1];}for (int i = n – 1; i >= 0; –i){sa[–buc[x[y[i]]]] = y[i];}int i;for (swap(x, y), x[sa[0]] = 0, p = 1, i = 1; i < n; ++i){x[sa[i]] = cmp(y, sa[i – 1], sa[i], l) ? p – 1 : p++;}}}void getheight(){int h = 0, n = size;for (int i = 0; i <= n; ++i){Rank[sa[i]] = i;}height[0] = 0;for (int i = 0; i < n; ++i){if (h > 0){–h;}int j =sa[Rank[i] – 1];for (; i + h < n && j + h < n && init[i + h] == init[j + h]; ++h);height[Rank[i] – 1] = h;}}//预处理每一个数字的对数，用于rmq，，常数优化void initLOG(){LOG[0] = -1;for (int i = 1; i < N; ++i){LOG[i] = (i & (i – 1)) ? LOG[i – 1] : LOG[i – 1] + 1;}}void initRMQ(){initLOG();int n = size;int limit;for (int i = 0; i < n; ++i){dp[i][0] = height[i];}for (int j = 1; j <= LOG[n]; ++j){limit = (n – (1 << j));for (int i = 0; i <= limit; ++i){dp[i][j] = min(dp[i][j – 1], dp[i + (1 << (j – 1))][j – 1]);}}}int LCP(int a, int b){int t;a = Rank[a];b = Rank[b];if (a > b){swap(a, b);}–b;t = LOG[b – a + 1];return min(dp[a][t], dp[b – (1 << t) + 1][t]);}void solve(int p, int q){int ans = 0;for (int i = 1; i <= size; ++i){//实际长度范围int r = size – sa[i];int l = height[i – 1] + 1;if (q <= r && q >= l){ans += q – max(l, p) + 1;}else if (q > r && p <= r){ans += r – max(l, p) + 1;}}printf(“%d\n”, ans);}}SA;int main(){int t;int p, q;scanf(“%d”, &t);int icase = 1;while (t–){SA.clear();scanf(“%s”, str);scanf(“%d%d”, &p, &q);int len = strlen(str);for (int i = 0; i < len; ++i){SA.insert(str[i] – ‘a’ + 1);}SA.getsa(30);SA.getheight();printf(“Case %d: “, icase++);SA.solve(p, q);}return 0;}
喜欢就该珍惜，珍惜就别放弃。
