【题解】SPOJ - LCS - Longest Common Substring

题目

http://www.spoj.com/problems/LCS/

题意

求两个串的最长公共连续子串。

题解

  • 后缀自动机经典题(听说用 \(O(n\log n)\) 的算法会超时)。
  • 对第一个串建 SAM,然后用第二个串在上面跑。
  • 依次考虑第二个串的每一个字符,以该字符结尾的后缀中,设最多能匹配 \(k\) 个字符,此时到达的状态为 \(s\)
  • 对于下一个字符 \(c\),如果存在 \(s\) 经过 \(c\) 的转移,那么就进入新状态,同时 \(k\) 增加 \(1\)
  • 如果不存在这样的转移,那只能从当前的最长匹配中舍弃首部的尽可能少的若干个字符,使得能够转移。也就是利用 SAM 中的 fa 指针转移,设最近的能够用 \(c\) 转移的状态是 \(s'\), 那么丢弃若干个字符后还剩下的长度是 \(len(s')\),然后再用 \(c\) 转移。
  • 特别的,如果 \(c\) 在原串中不存在(也就是没找到能用 \(c\) 转移的状态 \(s'\)),那么回到初始态重新计数。
  • 复杂度 O(n)。
  • 这个匹配的过程相当于滑动窗口(尺取法)。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 3E5 + 100;

namespace SAM {
const int M = maxn << 1;
int t[M][26], len[M] = {-1}, fa[M], sz = 2, last = 1;
void ins(int ch) {
int p = last, np = last = sz++;
len[np] = len[p] + 1;
while (p && !t[p][ch]) {
t[p][ch] = np; p = fa[p];
}
if (!p) { fa[np] = 1; return; }
int q = t[p][ch];
if (len[p] + 1 == len[q]) fa[np] = q;
else {
int nq = sz++; len[nq] = len[p] + 1;
memcpy(t[nq], t[q], sizeof t[0]);
fa[nq] = fa[q];
fa[np] = fa[q] = nq;
while (t[p][ch] == q) {
t[p][ch] = nq; p = fa[p];
}
}
}
int go(char* s) {
int ret = 0, cur = 1, cnt = 0;
FOR (i, 0, strlen(s)) {
int c = s[i] - 'a';
if (t[cur][c]) ++cnt;
else {
while (cur && !t[cur][c]) cur = fa[cur];
cnt = len[cur] + 1;
}
cur = cur ? t[cur][c] : 1;
ret = max(ret, cnt);
}
return ret;
}
}

char s[maxn];
int main() {
scanf("%s", s);
FOR (i, 0, strlen(s)) SAM::ins(s[i] - 'a');
scanf("%s", s);
cout << SAM::go(s) << endl;
}