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
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int k, pos, n, m=128, p, saa[200005], rnk[200005], tmp[200005], cnt[200005], hei[200005];
int sta[200005], top, wei[200005];
char ss[200005], ssb[100005];
void saSort(){
for(int i=0; i<m; i++) cnt[i] = 0;
for(int i=0; i<n; i++) cnt[rnk[tmp[i]]]++;
for(int i=1; i<m; i++) cnt[i] += cnt[i-1];
for(int i=n-1; i>=0; i--) saa[--cnt[rnk[tmp[i]]]] = tmp[i];
}
void buildSA(){
n++;
for(int i=0; i<n; i++){
rnk[i] = ss[i];
tmp[i] = i;
}
saSort();
for(int j=1; p<n; j<<=1){
p = 0;
for(int i=n-j; i<n; i++) tmp[p++] = i;
for(int i=0; i<n; i++)
if(saa[i]-j>=0)
tmp[p++] = saa[i] - j;
saSort();
swap(rnk, tmp);
p = 1;
rnk[saa[0]] = 0;
for(int i=1; i<n; i++)
if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])
rnk[saa[i]] = p - 1;
else
rnk[saa[i]] = p++;
m = p;
}
n--;
}
void getHeight(){
int h=0;
for(int i=1; i<=n; i++) rnk[saa[i]] = i;
for(int i=0; i<n; i++){
if(h) h--;
int p=saa[rnk[i]-1];
while(ss[i+h]==ss[p+h]) h++;
hei[rnk[i]] = h;
}
}
ll sol(bool isSa){
ll cont=0, re=0;
top = 0;
for(int i=2; i<=n; i++){
if(hei[i]<k) cont = top = 0;
else{
int weight=0;
if((isSa && saa[i-1]<pos) || (!isSa && saa[i-1]>pos)){
weight++;
cont += hei[i] - k + 1;
}
while(top && hei[i]<=sta[top]){
cont -= (ll)(sta[top] - hei[i]) * wei[top];
weight += wei[top];
top--;
}
sta[++top] = hei[i];
wei[top] = weight;
if((isSa && saa[i]>pos) || (!isSa && saa[i]<pos)) re += cont;
}
}
return re;
}
int main(){
while(scanf("%d", &k)!=EOF){
if(!k) break;
m = 128; p = 0;
scanf("%s %s", ss, ssb);
pos = strlen(ss); int len=strlen(ssb);
ss[pos] = '$';
for(int i=0; i<len; i++)
ss[pos+i+1] = ssb[i];
n = pos + len + 1;
ss[n] = 0;
buildSA();
getHeight();
printf("%lld\n", sol(true)+sol(false));
}
return 0;
}
|