知识点：SAM，RMQ
随手刷到的题一看是串串就做下。
这题面好随便啊呃呃
简述
给定一仅包含小写字母 \(a,b\) 的两个字符串 \(s, t\)，给定 \(q\) 次询问，每次给定参数 \(l, r\)，求 \(s[l:r]\) 与 \(t\) 的最长公共子串长度。
\(1\le |s|, |t|, q\le 2\times 10^5\)。
1S，512MB。
好像是套路，但我不会，学习了。
设 \(a_i\) 为前缀 \(s[1:i]\) 作为 \(t\) 的子串的最长的后缀的长度，即有：
\[a_i = \max_{1\le k\le i,\ s[i-k+1:i]\in t } \{ k \} \]先对 \(t\) 建 SAM，则 \(a_i\) 可以通过在 SAM 上匹配 \(s\) 得到，详见：「双串最长公共子串」SP1811 LCS - Longest Common Substring。则对于询问 \([l, r]\)，考虑最长公共子串是否是以 \(i(l\le i\le r)\) 结尾，则答案即为：
\[\max_{l\le i\le r}\left\{ \min\left( a_i, i - l + 1 \right) \right\} \]发现上式中当 \(i+1\) 时，\(i-l+1\) 也加 1，而 \(a_i\) 至多加 1 或者减少。可通过子串的性质反证 \(a_i\) 不可能增加大于等于 2。则一定存在 \(p(l\le p\le r)\)，满足：
\[\begin{cases} \min(a_i, i - l + 1) &= i - l + 1 &(i<p)\\ \min(a_i, i - l + 1) &= a_i &(p\le i) \end{cases}\]即上式等于：
\[\max\left\{(p - 1) - l + 1, \max_{p\le i\le r} a_i\right\} \]则可以对 \(a\) 维护 ST 表，每次询问先二分求得 \(p\) 后查询区间最大值即可。
总时间复杂度 \(O(|t| + |s| + m\log |s|)\) 级别。
代码
//知识点：SAM，RMQ
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, q;
int a[kN];
char s[kN], t[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
namespace SAM {
const int kNode = kN << 2;
int nodenum = 1, last = 1, tr[kNode][26], len[kNode], link[kNode];
int edgenum, head[kNode], v[kNode], ne[kNode];
int sz[kNode];
LL ans = 0;
void Insert(int ch_) {
int p = last, now = last = ++ nodenum;
len[now] = len[p] + 1;
sz[now] = 1;
for (; p && !tr[p][ch_]; p = link[p]) tr[p][ch_] = now;
if (!p) {
link[now] = 1;
return ;
}
int q = tr[p][ch_];
if (len[q] == len[p] + 1) {
link[now] = q;
return ;
}
int newq = ++ nodenum;
memcpy(tr[newq], tr[q], sizeof (tr[q]));
len[newq] = len[p] + 1;
link[newq] = link[q], link[q] = link[now] = newq;
for (; p && tr[p][ch_] == q; p = link[p]) tr[p][ch_] = newq;
}
void Build(int n_, char *s_) {
for (int i = 1; i <= n_; ++ i) Insert(s_[i] - 'a');
}
void Solve(int n_, char *s_) {
int now = 1, nowlen = 0;
for (int i = 1; i <= n_; ++ i) {
while (now != 1 && !tr[now][s_[i] - 'a']) now = link[now], nowlen = len[now];
if (tr[now][s[i] - 'a']) now = tr[now][s[i] - 'a'], ++ nowlen;
a[i] = nowlen;
}
}
}
namespace ST {
int Log2[kN], f[kN][21];
void Init() {
Log2[1] = 0;
for (int i = 2; i <= n; ++ i) Log2[i] = Log2[i >> 1] + 1;
for (int i = 1; i <= n; ++ i) f[i][0] = a[i];
for (int i = 1, l = 2; i <= 20; ++ i, l <<= 1) {
for (int j = 1; j + l - 1 <= n; ++ j) {
f[j][i] = std::max(f[j][i - 1], f[j + l / 2][i - 1]);
}
}
}
int Query(int l_, int r_) {
if (l_ > r_) return 0;
int l = Log2[r_ - l_ + 1];
return std::max(f[l_][l], f[r_ - (1 << l) + 1][l]);
}
}
int Query(int l_, int r_) {
int pos = r_ + 1;
for (int nowl = l_, nowr = r_; nowl <= nowr; ) {
int mid = (nowl + nowr) >> 1;
if (a[mid] < mid - l_ + 1) {
nowr = mid - 1;
pos = mid;
} else {
nowl = mid + 1;
}
}
return std::max(ST::Query(pos, r_), pos - 1 - l_ + 1);
return 0;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
scanf("%s", s + 1); n = strlen(s + 1);
scanf("%s", t + 1); m = strlen(t + 1);
SAM::Build(m, t);
SAM::Solve(n, s);
ST::Init();
q = read();
while (q --) {
int l_ = read(), r_ = read();
printf("%d\n", Query(l_ ,r_));
}
return 0;
}
/*
aaba
aaaabbbaa
1
2 4
aababaababbabaabbabbaabababaabbabbbabaaaaaababbaaa
bbaaabbabbaaaabbaabbaabbbabababbbaababababaaabbbbb
1
41 44
*/