description:
There are two strings \(a\), \(b\) with the length \(n\), and \(m\).
Find the Array <\(p_1, p_2, ..., p_m>\), such that \(a_{p_i}= b_i\), \(\max\{p_{i+1}-p_i\}\) is max.
solution:
Let array left mark the left-first find \(p_i\), right mark the right-first find \(p_i\).
The answer is :
\(\max_{i=1}^{m-1}\{right[i+1]- left[i]\}\)
code:
#include<cstdio>
const int N = 2e5 + 1;
const int inf = -1e9;
char a[N], b[N];
int left[N], right[N];
int main() {
int n, m;
scanf("%d%d%s%s", &n, &m, a, b);
int last = -1;
for (int i = 0; i < m; ++i) {
while (a[++last] != b[i]);
left[i] = last;
}
last = n;
for (int i = m - 1; i >= 0; --i) {
while (a[--last] != b[i]);
right[i] = last;
}
int ans = inf;
for (int i = 1; i < m; ++i) {
int cur = right[i] - left[i - 1];
if (cur > ans)ans = cur;
}
printf("%d\n", ans);
}