题目描述
难度分:1700
输入两个长度≤105的字符串s和t,只包含小写英文字母,保证t是s的一个子序列。
删除s中的最长子串,使得t仍然是s的子序列,输出这个最长子串的长度。
输入样例1
bbaba
bb
输出样例1
3
输入样例2
baaba
ab
输出样例2
2
输入样例3
abcde
abcde
输出样例3
0
输入样例4
asdfasdf
fasd
输出样例4
3
算法
双指针+前后缀分解
令s串的长度为n,t串的长度为m,预处理出pre和suf两个O(n)级别的数组。pre[i]表示s的前缀[1,i]匹配了t的前缀[1,pre[i]],suf[i]表示s的后缀[i,n]匹配了t的后缀[suf[i],m]。
先考虑删除前后缀的情况,遍历i∈[1,n],一旦满足pre[i]=m,说明删除s的后缀(i,n]可以使得t是s前缀[1,i]的子序列,维护n−i的最大值。倒序遍历i∈[1,n],一旦满足suf[i]=1,说明删除s的前缀[1,i)可以使得t是s后缀[i,n]的子序列。
最后是一般情况,我们希望某个s的前缀[1,i]能够匹配t的前缀,而这个t剩下的那部分,由某个s的后缀[j,n]完成匹配,这时候由pre[i]+1=suf[j]成立,维护j−i−1的最大值。还是倒序遍历i∈[1,n],对于某个i,为了快速求得这个j,可以开一个哈希表mp存储suf的值。当遍历到i时,看看pre[i]+1是否在哈希表中,在就说明存在符合条件的j。为了让j−i−1尽可能大,只有在suf[i]第一次出现的时候,存储mp[suf[i]]=i。
复杂度分析
时间复杂度
双指针匹配子序列,预处理出pre和suf两个数组,时间复杂度为O(n+m)。后续求答案遍历了3遍数组,一共三种情况:删除前缀、删除后缀、删除中间段。时间复杂度是O(n)的,因此整个算法的时间复杂度为O(n+m)。
空间复杂度
除了输入的s串和t串,开辟的辅助空间主要在于pre数组和suf数组,都是O(n)级别的。存suf值的哈希表mp,在最差情况下会存O(n)级别的键值对。因此,算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, pre[N], suf[N];
char s[N], t[N];
int main() {
scanf("%s", s + 1);
scanf("%s", t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
for(int i = 1; i <= n; i++) {
pre[i] = suf[i] = -1;
}
pre[0] = 0;
suf[n + 1] = m + 1;
int i = 1, j = 1;
while(i <= n && j <= m) {
if(s[i] == t[j]) {
pre[i] = j;
j++;
}
i++;
}
i = n, j = m;
while(i >= 1 && j >= 1) {
if(s[i] == t[j]) {
suf[i] = j;
j--;
}
i--;
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(pre[i] == m) {
ans = n - i;
break;
}
}
for(int i = n; i >= 1; i--) {
if(suf[i] == 1) {
ans = max(ans, i - 1);
break;
}
}
unordered_map<int, int> mp;
for(int i = n; i >= 1; i--) {
if(mp.count(pre[i] + 1)) {
ans = max(ans, mp[pre[i] + 1] - i - 1);
}
if(!mp.count(suf[i])) {
mp[suf[i]] = i;
}
}
printf("%d\n", ans);
return 0;
}