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
|
using namespace std;
const int maxn = 1e5;
char s[maxn], s1[maxn], s2[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n,m,k;
int r[maxn],h[maxn];
int ans;
void (int n,int m){
int i,*x = t,*y = t2;
for(i=0;i<m;i++)c[i] = 0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]] = i;
for(int k=1;k<=n;k<<=1){
int p = 0;
for(i=n-k;i<n;i++)y[p++] = i;
for(i=0;i<n;i++)if(sa[i]>=k)y[p++] = sa[i]-k;
for(i=0;i<m;i++)c[i] = 0;
for(i=0;i<n;i++)c[x[y[i]]]++;
for(i=0;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]] = y[i];
swap(x,y);
p = 1;x[sa[0]] = 0;
for(i=1;i<n;i++)
x[sa[i]] = y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n)break;
m = p;
}
}
void getheight(){
int i,j,k = 0;
for(i=0;i<=n;i++)r[sa[i]] = i;
for(i=0;i<n;i++){
if(k)k--;
if(!r[i])continue;
int j = sa[r[i]-1];
while(s[i+k]==s[j+k])k++;
h[r[i]] = k;
}
}
void solve(){
ans = 1e9;
for(int i = 1; i <= n; i++){
if(!h[i])continue;
if((sa[i] > m && sa[i - 1] < m) || (sa[i] < m && sa[i - 1] > m));
else continue;
if(i == 1 && h[i + 1] < h[i])ans = min(ans, h[i + 1] + 1);
else if(i == n && h[i - 1] < h[i]) ans = min(ans, h[i - 1] + 1);
else if(h[i - 1] < h[i] && h[i] > h[i + 1])ans = min(ans, max(h[i - 1], h[i + 1]) + 1);
}
}
int main(){
scanf("%s%s", s1, s2);
n = strlen(s1) + strlen(s2) + 1;
m = strlen(s1);
strcpy(s, s1);
s[m] = '#';
s[m + 1] = '
|
近期评论