http://codeforces.com/contest/762/problem/C
第一個串str[],第二個sub[]
預處理出prefix[i]表示sub的前i位和str[]的最長lcs去到str[]的最小的位置,如果某一位i不成立了,就設為inf
由于處理的時候,指針指向str[]的是單調遞增的,是以預處理複雜度O(n),同樣預處理suffix數組。
那麼就是求一個位置,使得兩個數組不會相交。
但是如果會相交,那麼應該讓那個數組退後一步呢,一開始用數組相鄰差的絕對值來确定,因為移動得多的那個必定更優。
但是不然,test5就知道了。
于是乎就直接處理出所有的prefix[i],所對應的最優suffix[],這個可以在suffix[]中二分搞定。
話說二分可真有用。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
vector<int>pos[26];
const int maxn = 1e5 + 20;
char str[maxn], sub[maxn];
int lenstr, lensub;
int L, R;
int prefix[maxn];
int suffix[maxn];
void init() {
int p1 = 0;
for (int i = 1; i <= lensub; ++i) {
if (pos[sub[i] - 'a'].size() == 0) break;
if (pos[sub[i] - 'a'].back() <= p1) break;
prefix[i] = upper_bound(pos[sub[i] - 'a'].begin(), pos[sub[i] - 'a'].end(), p1) - pos[sub[i] - 'a'].begin();
prefix[i] = pos[sub[i] - 'a'][prefix[i]];
p1 = prefix[i];
}
// for (int i = 1; i <= lensub; ++i) {
// cout << prefix[i] << " ";
// }
p1 = lenstr;
for (int i = lensub; i >= 1; --i) {
while (p1 >= 1) {
if (str[p1] == sub[i]) break;
p1--;
}
if (p1 == 0) break;
suffix[i] = p1;
p1--;
}
// for (int i = 1; i <= lensub; ++i) {
// cout << suffix[i] << " ";
// }
}
void work() {
scanf("%s%s", str + 1, sub + 1);
lenstr = strlen(str + 1);
lensub = strlen(sub + 1);
memset(prefix, 0x3f, sizeof prefix);
memset(suffix, -1, sizeof suffix);
for (int i = 1; i <= lenstr; ++i) {
pos[str[i] - 'a'].push_back(i);
}
prefix[0] = -1;
suffix[lensub + 1] = inf;
init();
int pos1 = inf, pos2 = inf;
for (int i = 1; i <= lensub; ++i) {
if (prefix[i] == inf) {
pos1 = i - 1;
break;
}
}
for (int i = lensub; i >= 1; --i) {
if (suffix[i] == -1) {
pos2 = i + 1;
break;
}
}
if (prefix[1] == inf && suffix[lensub] == -1) {
cout << "-" << endl;
return;
}
if (pos1 == inf || pos2 == inf) {
cout << sub + 1 << endl;
return;
}
if (pos1 == 0) {
assert(pos2 != lensub + 1);
for (int i = pos2; i <= lensub; ++i) {
printf("%c", sub[i]);
}
return;
}
if (pos2 == lensub + 1) {
for (int i = 1; i <= pos1; ++i) {
printf("%c", sub[i]);
}
return;
}
int anslen = -1;
for (int i = 0; i <= pos1; ++i) {
int topos = upper_bound(suffix + pos2, suffix + 1 + lensub, prefix[i]) - suffix;
// cout << suffix[topos] << endl;
if (anslen < i + lensub - topos + 1) {
anslen = i + lensub - topos + 1;
L = i + 1;
R = topos - 1;
}
}
// cout << L << " " << R << endl;
for (int i = 1; i <= lensub; ++i) {
if (i == L) {
i = R;
continue;
}
printf("%c", sub[i]);
}
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return 0;
}