HDU 3518 Boring counting

Boring counting

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3518
64-bit integer IO format: %I64d Java class name: Main

035 now faced a tough problem,his english teacher gives him a string,which consists with n lower case letter,he must figure out how many substrings appear at least twice,moreover,such apearances can not overlap each other.
Take aaaa as an example.”a” apears four times,”aa” apears two times without overlaping.however,aaa can’t apear more than one time without overlaping.since we can get “aaa” from [0-2](The position of string begins with 0) and [1-3]. But the interval [0-2] and [1-3] overlaps each other.So “aaa” can not take into account.Therefore,the answer is 2(“a”,and “aa”).

Input

The input data consist with several test cases.The input ends with a line “#”.each test case contain a string consists with lower letter,the length n won’t exceed 1000(n <= 1000).

Output

For each test case output an integer ans,which represent the answer for the test case.you’d better use int64 to avoid unnecessary trouble.

Sample Input

aaaa
ababcabb
aaaaaa
#

Sample Output

2
3
3

Source

2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU

解题：后缀数组。。。。后缀数组学习中

 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 = 100100;
18 int n,k,_rank[maxn],tmp[maxn],sa[maxn],lcp[maxn];
19 string str;
20 bool cmp_sa(int i,int j){
21     if(_rank[i] != _rank[j]) return _rank[i] < _rank[j];
22     int ri = i+k <= n ? _rank[i+k]:-1;
23     int rj = j+k <= n ? _rank[j+k]:-1;
24     return ri < rj;
25 }
26 void construct_sa(string &S,int *sa){
27     for(int i = 0; i <= n; i++){
28         sa[i] = i;
29         _rank[i] = i < n ? S[i]:-1;
30     }
31     for(k = 1; k <= n; k <<= 1){
32         sort(sa,sa+n+1,cmp_sa);
33         tmp[sa[0]] = 0;
34         for(int i = 1; i <= n; i++)
35             tmp[sa[i]] = tmp[sa[i-1]] + cmp_sa(sa[i-1],sa[i]);
36         for(int i = 0; i <= n; i++) _rank[i] = tmp[i];
37     }
38 }
39 void construct_lcp(string &S,int *sa,int *lcp){
40     for(int i = 0; i <= n; i++) _rank[sa[i]] = i;
41     int h = lcp[0] = 0;
42     for(int i = 0; i < n; i++){
43         int j = sa[_rank[i]-1];
44         if(h > 0) h--;
45         for(; j + h < n && i + h < n; h++)
46             if(S[j+h] != S[i+h]) break;
47         lcp[_rank[i]-1] = h;
48     }
49 }
50 bool can(int n,int len,int &ans){
51     int theMin = sa[1],theMax = sa[1];
52     bool flag = false;
53     for(int i = 1; i < n; i++){
54         if(lcp[i] < len){
55             if(theMax - theMin >= len) {flag = true;ans++;}
56             theMin = theMax = sa[i+1];
57             continue;
58         }
59         if(sa[i+1] > theMax) theMax = sa[i+1];
60         if(sa[i+1] < theMin) theMin = sa[i+1];
61     }
62     return flag;
63 }
64 int main() {
65     while(cin>>str,str[0] != '#'){
66         n = str.length();
67         memset(sa,0,sizeof(sa));
68         memset(lcp,0,sizeof(lcp));
69         construct_sa(str,sa);
70         construct_lcp(str,sa,lcp);
71         int ans = 0;
72         for(int len = 1; len < n; len++)
73             if(!can(n+1,len,ans)) break;
74         printf("%d
",ans);
75     }
76     return 0;
77 }

View Code

后缀自动机

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 5010;
 5 int L[maxn],R[maxn],c[maxn],sa[maxn];
 6 struct node{
 7     int son[26],f,len;
 8     void init(){
 9         memset(son,-1,sizeof son);
10         len = 0;
11         f = -1;
12     }
13 };
14 struct SAM{
15     node e[maxn];
16     int tot,last;
17     int newnode(int len = 0){
18         e[tot].init();
19         e[tot].len = len;
20         return tot++;
21     }
22     void init(){
23         tot = last = 0;
24         newnode();
25     }
26     void add(int c){
27         int p = last,np = newnode(e[p].len + 1);
28         while(p != -1 && e[p].son[c] == -1){
29             e[p].son[c] = np;
30             p = e[p].f;
31         }
32         if(p == -1) e[np].f = 0;
33         else{
34             int q = e[p].son[c];
35             if(e[p].len + 1 == e[q].len) e[np].f = q;
36             else{
37                 int nq = newnode();
38                 e[nq] = e[q];
39                 e[nq].len = e[p].len + 1;
40                 e[q].f = e[np].f = nq;
41                 while(p != -1 && e[p].son[c] == q){
42                     e[p].son[c] = nq;
43                     p = e[p].f;
44                 }
45             }
46         }
47         last = np;
48         L[np] = R[np] = e[np].len;
49     }
50 }sam;
51 char str[maxn];
52 int main(){
53     while(scanf("%s",str),str[0] != '#'){
54         int len = strlen(str);
55         sam.init();
56         for(int i = 0; i < maxn; ++i){
57             L[i] = len + 1;
58             R[i] = -1;
59             c[i] = 0;
60         }
61         for(int i = 0; str[i]; ++i)
62             sam.add(str[i] - 'a');
63         node *e = sam.e;
64         for(int i = 0; i < sam.tot; ++i) c[e[i].len]++;
65         for(int i = 1; i <= len; ++i) c[i] += c[i-1];
66         for(int i = sam.tot-1; i >= 0; --i) sa[--c[e[i].len]] = i;
67         for(int i = sam.tot-1; i > 0; --i){
68             int v = sa[i];
69             L[e[v].f] = min(L[e[v].f],L[v]);
70             R[e[v].f] = max(R[e[v].f],R[v]);
71         }
72         LL ret = 0;
73         for(int i = 1; i < sam.tot; ++i)
74             if(R[i] - L[i] > e[e[i].f].len) 
75                 ret += min(R[i] - L[i],e[i].len) - e[e[i].f].len;
76         printf("%I64d
",ret);
77     }
78     return 0;
79 }

View Code