HDU 4622 Reincarnation
题意： 长度为2000的串，10000个询问：[l,r]这个子串包含多少不同的子串。
比赛时用的后缀数组o(nQ) ，赛后用的hash o(nn*log(n)) 和后缀自动机，这个log的出现是因为hash写不来 = = .
后缀数组解发：
先对原来的串做一遍后缀数组，对于每个询问,对sa数组进行扫描，如果当前前缀在[l,r]范围内，就找到之前和他公共前缀最长且也在[l,r]范围内的串，lcp最长公共前缀，答案加上 串在当前询问中的长度减去最长公共前缀。
值得注意的是和当前串公共前缀最长的并不就是上一次在[l,r]范围内的串，也有可能是再之前，原因是询问的区间，相当于给每个串截断了一部分，所以区间里sa数组不再代表这区间里的串的排名，处理比较容易，见代码
1 |
|
hash解法：
用hash把所有相同的子串放在一起，[l1,r1] [l2,r2]。。。现在对于每一个询问，只把这个串第一次出现的算是这个询问的也就是询问[L，R]， 满足 l1<L<=l2 ,R>=r2时[l2,r2]算给他。
然后利用扫描线和部分和维护，对于子串[l2,r2] ，g[r2][l1+1] 加1 , g[r2][l2+1]减1，对于所有r，从左到右求一遍部分和，再从上到下求一遍部分和，g[r][l]就是询问l,r的答案了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90//#pragma comment(linker, "/STACK:65536000")
using namespace std;
char s[20005];
uint hash[2100],w[2005][2005];;
uint seed = 131;
pair<short,short> a[2100];
int g[2005][2005];
int n,m;
int search(uint val){
int l = 0 , r = m-1;
while(r-l>1){
int mid = (l+r)/2;
if(hash[mid] < val) l = mid;
else r = mid;
}
if(hash[l] == val) return l;
else return r;
}
int main(){
// freopen("/home/zyc/Documents/Code/cpp/in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s);
n = strlen(s);
for(int i=0;i<n;i++){
uint val = 0;
for(int j=i;j<n;j++){
val = val*seed + s[j];
w[i][j] = (val & 0x7FFFFFFF) ;
}
}
for(int i=0;i<n;i++) for(int j=0;j<n;j++) g[i][j]=0;
for(int d=1;d<=n;d++){
m = 0;
for(int i=0;i<n-d+1;i++)
hash[m++] = w[i][i+d-1];
sort(hash,hash+m);
int l = 1;
for(int i=1;i<m;i++){
if(hash[i] != hash[l-1])
hash[l++] = hash[i];
}
m = l;
for(int i=0;i<m;i++) a[i] = make_pair(-1,-1);
for(int i=0;i<n-d+1;i++){
uint val = w[i][i+d-1];
int p = search(val);
int r = i+d-1;
int l1,l2;
if(a[p].first == -1) l1 = -1;
else l1 = a[p].first;
l1++;
l2 = i;
g[r][l1]++;
g[r][l2+1] --;
a[p] = make_pair(i,i+d-1);
}
}
for(int i=0;i<n;i++)
for(int j=1;j<n;j++)
g[i][j] += g[i][j-1];
for(int j=0;j<n;j++)
for(int i=1;i<n;i++)
g[i][j] += g[i-1][j];
int Q;
scanf("%d",&Q);
while(Q--){
int l,r;
scanf("%d%d",&l,&r);
r--;
l--;
printf("%d\n",g[r][l]);
}
}
return 0;
}
后缀自动机：预处理，解法不多说。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
using namespace std;
const int ch = 26;
const int N=100000;
class SAM{
public:
int f[N],chd[N][ch+1],len[N],sw[200];
//ch+1 number of tempt suffix at status
int last,sz;
void init(){
clr(chd[0],0);
f[0] = -1;
chd[0][ch] = 1;
last = 0;
sz = 0;
for(int i=0;i<26;i++)
sw[i+'a'] = i;
}
int add(char inc,int l){
int ans = 0;
int c = sw[inc];
int x = last;
last = ++sz;
clr(chd[sz],0);
len[sz] = l;
for(;x!=-1&&chd[x][c]==0;x=f[x]){
chd[x][c] = sz;
chd[last][ch] += chd[x][ch];
ans += chd[x][ch];
}
if(x == -1){
f[sz]=0;
}
else{
int y = chd[x][c];
if(len[y] == len[x]+1){
f[sz]=y;
}
else{
sz++;
len[sz] = len[x] + 1;
for(int i=0;i<ch;i++) chd[sz][i] = chd[y][i];
chd[sz][ch] = 0;
f[sz] = f[y];
f[last] = f[y] = sz;
for(;x!=-1&&chd[x][c]==y;x=f[x]){
chd[x][c] = sz;
chd[y][ch] -= chd[x][ch];
chd[sz][ch] += chd[x][ch];
}
}
}
return ans;
}
}sam;
char s[100000];
int n,m;
int g[2005][2005];
int main(){
// freopen("/home/zyc/Documents/Code/cpp/in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s);
n = strlen(s);
for(int i=0;i<n;i++){
sam.init();
for(int j=i;j<n;j++){
if(j!=i)
g[i][j] = g[i][j-1] + sam.add(s[j],j-i+1);
else
g[i][j] = sam.add(s[j],j-i+1);
}
}
int Q;
scanf("%d",&Q);
while(Q--){
int l,r;
scanf("%d%d",&l,&r);
l--;r--;
printf("%d\n",g[l][r]);
}
}
return 0;
}