CF427 D Match & Catch

CF427 D Match & Catch

CF427 D Match & Catch

题意

给出两个字符串,求出两个字符串中的最短公共子串,且在每个字符串中只出现过一次

思路

考虑把两个字符串合并起来,求出$sa$,$rk$和$Height$数组,我们可以从小到大枚举子串长度$k$,然后再枚举后缀

具体来说,我们是根据子串字典序从小到大枚举后缀的,如果$Height[i]$不小于$k$

(即第$i-1$个子串和第$i$个子串的最长公共前缀不小于$k$),并且如果此后缀的起始点在第一个字符串

则$cnt1++$,否则$cnt2++$

$cnt1$和$cnt2$分别代表最长公共子串出现在第一个字符串和第二个字符串的次数

由于是连续更新的,所以假如上一轮$cnt1=1$,现在更新$cnt2=1$

那么说明这两个子符串有相同的长度大于$k$的公共子串,但是不是唯一还不知道

也就是说这个数字只在两轮更新中有用,如果$cnt1>1$或$cnt2>1$都没有价值了

(要么没有公共子串,要么有重复的)

如果要确保唯一性,就要当$Height[i]$枚举到小于$k$的时候,如果此时$cnt1 == 1 $ $and$ $ cnt2 == 1$的话,则有解。

题解代码

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
102
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1, s2, str;
int len1, tot, m;
const int MAXN = 10004;
int a[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], sa[MAXN], rk[MAXN];

void RSort()
{
for (int i = 1; i <= m; i++)
tax[i] = 0;
for (int i = 1; i <= tot; i++)
tax[rk[i]]++;
for (int i = 1; i <= m; i++)
tax[i] += tax[i - 1];
for (int i = tot; i >= 1; i--)
sa[tax[rk[tp[i]]]--] = tp[i];
}

bool cmp(int *f, int x, int y, int w)
{
return f[x] == f[y] && f[x + w] == f[y + w];
}

void Suffix()
{
m = 127;
for (int i = 1; i <= tot; i++)
rk[i] = a[i], tp[i] = i;
int p = 0;
RSort();
for (int w = 1; p < tot; w += w, m = p)
{
p = 0;
for (int i = tot - w + 1; i <= tot; i++)
tp[++p] = i;
for (int i = 1; i <= tot; i++)
if (sa[i] > w)
tp[++p] = sa[i] - w;
RSort();
swap(rk, tp);
rk[sa[1]] = p = 1;
for (int i = 2; i <= tot; i++)
rk[sa[i]] = cmp(tp, sa[i], sa[i - 1], w) ? p : ++p;
}
int j = 0, k = 0;
for (int i = 1; i <= tot; Height[rk[i++]] = k)
{
for (k = k ? k - 1 : k, j = sa[rk[i] - 1]; a[i + k] == a[j + k]; k++)
;
}
}

bool solve(int k, int div)
{
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= tot; i++)
{
if (Height[i] < k)
{
if (cnt1 == 1 && cnt2 == 1)
{
return true;
}
cnt1 = 0;
cnt2 = 0;
if (sa[i] <= div)
cnt1++;
else if (sa[i] >= div)
cnt2++;
continue;
}
if (sa[i] <= div)
cnt1++;
else if (sa[i] >= div)
cnt2++;
}
return cnt1 == 1 && cnt2 == 1; //如果枚举完了也要判断一下
}

int main()
{
cin >> s1 >> s2;
len1 = s1.length();
str = s1 + '#' + s2; //将两个字符串隔开来,避免sa等数组重叠
tot = len1 + s2.length() + 1;
for (int i = 1; i <= tot; i++)
a[i] = str[i - 1];
Suffix(); //后缀数组
int ans = -1;
for (int i = 1; i <= len1; i++)
{ //枚举长度
if (solve(i, len1))
{
ans = i;
break;
}
}
printf("%d\n", ans);
return 0;
}

重点解析

1
2
3
4
/*
后缀数组:
https://blog.csdn.net/Astinli/article/details/82495530
*/