题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3518
题意: 给出一个字符串, 问其中有多少字串出现了两次以上(计算次数时不能彼此覆盖, 如 "aaaa" 中 "aa" 出现了两次而非三次).
思路: 后缀数组/字典树
后缀数组解法, 题目所求即使用后缀中出现两次以上的前缀数目. 可以枚举前缀长度, 将满足条件的前缀累进答案中. 在 SA 数组中, 具有相同前缀的后缀肯定是在一个连续块中的. 可以用 height 数组的性质来区分当前长度有哪些前缀块. 注意满足条件的前缀块中至少存在两个彼此不覆盖的前缀.
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define rank Rank
using namespace std; const int MAXN = 1e4 + ;
char str[MAXN];
int SA[MAXN], rank[MAXN], height[MAXN], sum[MAXN], tp[MAXN], a[MAXN]; bool cmp(int *f, int x, int y, int w){
return f[x] == f[y] && f[x + w] == f[y + w];
} void get_SA(int *s, int n, int m){
for(int i = ; i < m; i++) sum[i] = ;
for(int i = ; i < n; i++) sum[rank[i] = s[i]]++;
for(int i = ; i < m; i++) sum[i] += sum[i - ];
for(int i = n - ; i >= ; i--) SA[--sum[rank[i]]] = i;
for(int len = ; len <= n; len <<= ){
int p = ;
for(int i = n - len; i < n; i++) tp[p++] = i;//后面i个数没有第二关键字,即第二关键字为空,所以最小
for(int i = ; i < n; i++){
if(SA[i] >= len) tp[p++] = SA[i] - len;
}
//tp[i]存储按第二关键字排序第i的下标
//对第二关键字排序的结果再按第一关键字排序,和长度为1的情况类似
for(int i = ; i < m; i++) sum[i] = ;
for(int i = ; i < n; i++) sum[rank[tp[i]]]++;
for(int i = ; i < m; i++) sum[i] += sum[i - ];
for(int i = n - ; i >= ; i--) SA[--sum[rank[tp[i]]]] = tp[i];
//根据SA和rank数组重新计算rank数组
swap(rank, tp);//交换后tp指向旧的rank数组
p = ;
rank[SA[]] = ;
for(int i = ; i < n; i++){
rank[SA[i]] = cmp(tp, SA[i - ], SA[i], len) ? p - : p++;
}
if(p >= n) break;
m = p;//下次基数排序的最大值
}
//求height
int k = ;
n--;
for(int i = ; i <= n; i++) rank[SA[i]] = i;
for(int i = ; i < n; i++){
if(k) k--;
int j = SA[rank[i] - ];
while(s[i + k] == s[j + k]) k++;
height[rank[i]] = k;
}
} int main(void){
while(~scanf("%s", str)){
if(str[] == '#') break;
int len = strlen(str), sol = ;
for(int i = ; i < len; i++) a[i] = str[i];
a[len] = ;
get_SA(a, len + , );
for(int i = ; i <= len / ; i++){
int l = MAXN, r = ;
for(int j = ; j <= len; j++){
if(height[j] >= i){
l = min(l, min(SA[j], SA[j - ]));
r = max(r, max(SA[j], SA[j - ]));
}else{
if(r - l >= i) sol++;
l = MAXN;
r = ;
}
}
if(r - l >= i) sol++;
}
printf("%d\n", sol);
}
return ;
}