You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a subsequence of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.
Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.
The first line contains string a, and the second line — string b. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.
On the first line output a subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.
If the answer consists of zero characters, output ?-? (a minus sign).
hi
bob
-
abca
accepted
ac
abacaba
abcdcba
abcba
In the first example strings a and b don‘t share any symbols, so the longest string that you can get is empty.
In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.
题目分析 ：
给出两个字符串，删除第二个字符串中的一些连续的字符，且要求剩下的字符是上面串的子串。
思路分析 ：
首先上来先想一个最暴力的思路，枚举删除字符串的长度，枚举删除的起点，再将剩下的字符串去匹配，双指针，复杂度是 n^3 , 首先比较容易想到的一个地方优化，就是枚举长度的时候我们可以去二分，复杂度为 logn ，但是仅凭这是不够的，我们看一下字符串匹配那，是不是感觉匹配的过程中有很多匹配过程是重复的，那么这里肯定就是可以优化的，当删除一个长度的字符串后，剩下的串一定是都要留下的，且可以看成一个前缀和一个后缀，那么我们就可以预处理出全部可能的前缀以及后缀，新开两个数组，记录的每个位置对应在上面串中的哪个位置上，那么总的复杂度就是 n*logn
代码示例 ：
#define ll long long
const int maxn = 1e5+5;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
char pre[maxn], s[maxn];
int a[maxn], b[maxn];
int len1, len2;
int start = -1, len;
bool check(int lenn) {
int p = lenn+1;
int sign = 0;
if (b[p]) {start = 1; len = lenn; sign = 1;}
p = len2 - lenn;
if (a[p]) {start = p+1; len = lenn; sign = 1;}
//printf("**** %d %d\n", start, len);
for(int i = 2; i <= len2-lenn; i++){
int ss = i-1, ee = i+lenn;
if (!a[ss]) break;
if (a[ss] < b[ee]) {start = i; len = lenn; sign = 1;}
}
if (sign) return true;
else return false;
}
void fun() {
int l = 0, r = len2;
while(l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
//printf("***** %d %d %d %d %d\n", start, len, mid, l, r);
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%s", pre+1);
scanf("%s", s+1);
len1 = strlen(pre+1);
len2 = strlen(s + 1);
int p = 1;
for(int i = 1; i <= len2; i++){
for(int j = p; j <= len1; j++){
if (s[i] == pre[j]) {
a[i] = j;
p = j+1;
break;
}
}
if (!a[i]) break;
}
p = len1;
for(int i = len2; i >= 1; i--){
for(int j = p; j >= 1; j--){
if (s[i] == pre[j]) {
b[i] = j;
p = j-1;
break;
}
}
if (!b[i]) break;
}
fun();
//printf("%d %d\n", start, len);
if (start == -1) {printf("-\n"); return 0;}
for(int i = 1; i < start; i++) printf("%c", s[i]);
for(int i = start+len; i <= len2; i++) printf("%c", s[i]);
printf("\n");
//for(int i = 1; i <= len2; i++) printf("%d ", b[i]);
return 0;
}