首页 > 代码库 > SPOJ 705 New Distinct Substrings
SPOJ 705 New Distinct Substrings
New Distinct Substrings
Time Limit: 2000ms
Memory Limit: 262144KB
This problem will be judged on SPOJ. Original ID: SUBST164-bit integer IO format: %lld Java class name: Main
Given a string, we need to find the total number of its distinct substrings.
Input
T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000
Output
For each test case output one number saying the number of distinct substrings.
Example
Input:2CCCCCABABAOutput:59
Source
Base on a problem in ByteCode06
解题:求不同子串的个数。后缀数组lcp的应用。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 50010;18 int rk[maxn],wb[maxn],wv[maxn],wd[maxn],lcp[maxn];19 bool cmp(int *r,int i,int j,int k){20 return r[i] == r[j] && r[i+k] == r[j+k];21 }22 void da(int *r,int *sa,int n,int m){23 int i,k,p,*x = rk,*y = wb;24 for(i = 0; i < m; ++i) wd[i] = 0;25 for(i = 0; i < n; ++i) wd[x[i] = r[i]]++;26 for(i = 1; i < m; ++i) wd[i] += wd[i-1];27 for(i = n-1; i >= 0; --i) sa[--wd[x[i]]] = i;28 29 for(p = k = 1; p < n; k <<= 1,m = p){30 for(p = 0,i = n-k; i < n; ++i) y[p++] = i;31 for(i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;32 for(i = 0; i < n; ++i) wv[i] = x[y[i]];33 34 for(i = 0; i < m; ++i) wd[i] = 0;35 for(i = 0; i < n; ++i) wd[wv[i]]++;36 for(i = 1; i < m; ++i) wd[i] += wd[i-1];37 for(i = n-1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];38 39 swap(x,y);40 x[sa[0]] = 0;41 for(p = i = 1; i < n; ++i)42 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;43 }44 }45 void calcp(int *r,int *sa,int n){46 for(int i = 1; i <= n; ++i) rk[sa[i]] = i;47 int h = 0;48 for(int i = 0; i < n; ++i){49 if(h > 0) h--;50 for(int j = sa[rk[i]-1]; i+h < n && j+h < n; h++)51 if(r[i+h] != r[j+h]) break;52 lcp[rk[i]-1] = h;53 }54 }55 int r[maxn],sa[maxn];56 char str[maxn];57 int main() {58 int n;59 scanf("%d",&n);60 while(n--){61 scanf("%s",str);62 int len = strlen(str);63 for(int i = 0; i < len; ++i)64 r[i] = str[i];65 r[len] = 0;66 da(r,sa,len+1,128);67 calcp(r,sa,len);68 int ans = 0;69 for(int i = 1; i <= len; ++i)70 ans += len - sa[i] - lcp[i];71 printf("%d\n",ans);72 }73 return 0;74 }
SPOJ 705 New Distinct Substrings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。