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: 2 CCCCC ABABA Output: 5 9
Source
解题：求不同子串的个数。后缀数组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 long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 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 ",ans); 72 } 73 return 0; 74 }
后缀自动机
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 char str[maxn]; 5 int ret,n; 6 struct SAM{ 7 struct node{ 8 int son[26],f,len; 9 void init(){ 10 f = -1; 11 len = 0; 12 memset(son,-1,sizeof son); 13 } 14 }e[maxn]; 15 int tot,last; 16 int newnode(int len = 0){ 17 e[tot].init(); 18 e[tot].len = len; 19 return tot++; 20 } 21 void init(){ 22 tot = last = 0; 23 newnode(); 24 } 25 void extend(int c){ 26 int p = last,np = newnode(e[p].len + 1); 27 while(p != -1 && e[p].son[c] == -1){ 28 e[p].son[c] = np; 29 p = e[p].f; 30 } 31 if(p == -1) e[np].f = 0; 32 else{ 33 int q = e[p].son[c]; 34 if(e[p].len + 1 == e[q].len) e[np].f = q; 35 else{ 36 int nq = newnode(); 37 e[nq] = e[q]; 38 e[nq].len = e[p].len + 1; 39 e[q].f = e[np].f = nq; 40 while(p != -1 && e[p].son[c] == q){ 41 e[p].son[c] = nq; 42 p = e[p].f; 43 } 44 } 45 } 46 last = np; 47 } 48 void solve(){ 49 ret = 0; 50 for(int i = 1; i < tot; ++i) 51 ret += e[i].len - e[e[i].f].len; 52 printf("%d ",ret); 53 } 54 }sam; 55 56 int main(){ 57 int kase; 58 scanf("%d",&kase); 59 while(kase--){ 60 scanf("%s",str); 61 n = strlen(str); 62 sam.init(); 63 for(int i = ret = 0; str[i]; ++i) 64 sam.extend(str[i]-'A'); 65 sam.solve(); 66 } 67 return 0; 68 }