要求 构建 splay mil 至少 ast discus 最小值
给出几个由小写字母构成的单词,求它们最长的公共子串的长度。任务:l 读入单词 l 计算最长公共子串的长度 l 输出结果
文件的第一行是整数 n ,表示单词的数量。接下来 n 行每行一个单词,只由小写字母组成,单词的长度至少为 1,最大为 2000。
仅一行,一个整数,最长公共子串的长度。
2 <= n <= 5
因为要求所有串的最长公共子串,所以我们运用 SAM,先对第一个串(基本串)构建一个 SAM,然后用后面的串匹配即可。
记录 L[i] 表示当前串和基本串在 i 这个状态匹配的最长长度。显然,一个状态对答案的贡献是所有串和基本串匹配时 L[i] 的最小值。
然后取一个最大值即可。
View Code
- 1#include 2#include < string > 3#include 4#include 5#include 6#include 7#include 8 using namespace std;
- 9 10 const int ONE = 4005;
- 11 const int INF = 2147483640;
- 12 13 int T,
- n;
- 14 char str[ONE];
- 15 int ans[ONE],
- q[ONE],
- L[ONE];
- 16 int len[ONE],
- a[ONE][27],
- fa[ONE],
- v[ONE];
- 17 int last,
- cnt;
- 18 int Ans;
- 19 20 int get() 21 {
- 22 int res = 1,
- Q = 1;
- char c;
- 23
- while ((c = getchar()) < 48 || c > 57) 24
- if (c == ' - ') Q = -1;
- 25 res = c - 48;
- 26
- while ((c = getchar()) >= 48 && c <= 57) 27 res = res * 10 + c - 48;
- 28
- return res * Q;
- 29
- }
- 30 31 struct SAM 32 {
- 33 SAM() {
- last = cnt = 1;
- }
- 34 void Add(int c) 35 {
- 36 int x = last,
- New = last = ++cnt;
- 37 len[New] = len[x] + 1;
- v[New] = 1;
- 38
- while (x && !a[x][c]) a[x][c] = New,
- x = fa[x];
- 39
- if (!x) {
- fa[New] = 1;
- return;
- }
- 40 41 int q = a[x][c];
- 42
- if (len[x] + 1 == len[q]) fa[New] = q;
- 43
- else 44 {
- 45 int Nq = ++cnt;
- len[Nq] = len[x] + 1;
- 46 memcpy(a[Nq], a[q], sizeof(a[q]));
- 47 fa[Nq] = fa[q];
- 48 fa[New] = fa[q] = Nq;
- 49
- while (a[x][c] == q) a[x][c] = Nq,
- x = fa[x];
- 50
- }
- 51
- }
- 52 53 void Pre() 54 {
- 55
- for (int i = 1; i <= cnt; i++) v[len[i]]++;
- 56
- for (int i = 1; i <= cnt; i++) ans[i] = len[i];
- 57
- for (int i = 1; i <= n; i++) v[i] += v[i - 1];
- 58
- for (int i = cnt; i >= 1; i--) q[v[len[i]]--] = i;
- 59
- }
- 60
- };
- 61 SAM S;
- 62 63 void Check() 64 {
- 65 memset(L, 0, sizeof(L));
- 66 n = strlen(str + 1);
- 67 int x = 1,
- record = 0;
- 68
- for (int i = 1; i <= n; i++) 69 {
- 70 int c = str[i] - 'a' + 1;
- 71
- while (x && !a[x][c]) x = fa[x];
- 72
- if (!x) {
- x = 1;
- record = 0;
- continue;
- }
- 73 record = min(record, len[x]) + 1;
- 74 x = a[x][c];
- 75 L[x] = max(L[x], record);
- 76
- }
- 77 78
- for (int i = cnt; i >= 1; i--) 79 L[fa[q[i]]] = max(L[fa[q[i]]], L[q[i]]);
- 80
- for (int i = 1; i <= cnt; i++) 81 ans[i] = min(ans[i], L[i]);
- 82
- }
- 83 84 int main() 85 {
- 86 T = get();
- T--;
- 87 scanf("%s", str + 1);
- n = strlen(str + 1);
- 88
- for (int i = 1; i <= n; i++) S.Add(str[i] - 'a' + 1);
- 89 S.Pre();
- 90 91
- while (T--) 92 {
- 93 scanf("%s", str + 1);
- 94 Check();
- 95
- }
- 96 97
- for (int i = 1; i <= cnt; i++) 98 Ans = max(Ans, ans[i]);
- 99 100 printf("%d", Ans);
- 101
- }
【BZOJ2946】公共串 [SAM]
来源: http://www.bubuko.com/infodetail-2071185.html