天天看點

C. Two strings 二分 + 預處理

​​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[]中二分搞定。

話說二分可真有用。

C. Two strings 二分 + 預處理
#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;
}