CF - 223 - B. Two Strings

題意：給出兩個由小寫字母組成的字符串s和t（長度都不超過2*10^5），問能否用t作為s的子序列把s的每一個字母都用過（s中的字母可以用多次）。

題目鏈接：http://codeforces.com/problemset/problem/223/B

——>>參考wuyiqi的想法：http://blog.csdn.net/crazy_ac/article/details/7999607

第一步：從左往右掃描s，記錄s[i]能匹配到t的最右位置L[i]；

第二步：從右往左掃描s，記錄s[i]能匹配到的t最左位置R[i]；

以上兩步，根據字母去找，如果一個字母已經匹配到了某個位置，那麼以後這個字母至少可以匹配到這個位置。

第三步：掃描判斷L與R，如果L[i]，R[i]匹配不上，或者L[i] < R[i]（此時說明s中不存在包含s[i]的子序列匹配t，假設存在，即使把s[i]分成兩個，一個匹配t的左邊到L[i]，一個匹配t的右邊到R[i]，但是t中L[i] < < R[i]的位置匹配不上，假設不成立）。

#include 
#include 

using namespace std;

const int maxn = 200000 + 10;

char s[maxn], t[maxn];
int L[maxn], R[maxn], last[maxn];

int main()
{
    while(scanf("%s%s", s, t) == 2) {
        memset(last, -1, sizeof(last));
        int j = 0, slen = strlen(s), tlen = strlen(t);
        for(int i = 0; i < slen; i++) {
            L[i] = last[s[i]-'a'];
            if(j < tlen && s[i] == t[j]) {
                L[i] = j;
                j++;
            }
            last[s[i]-'a'] = L[i];
        }
        memset(last, -1, sizeof(last));
        j = tlen - 1;
        for(int i = slen-1; i >= 0; i--) {
            R[i] = last[s[i]-'a'];
            if(j >= 0 && s[i] == t[j]) {
                R[i] = j;
                j--;
            }
            last[s[i]-'a'] = R[i];
        }
        bool ok = true;
        for(int i = 0; i < slen; i++)
            if(L[i] == -1 || R[i] == -1 || L[i] < R[i]) {
                ok = false;
                break;
            }
        ok ? puts("Yes") : puts("No");
    }
    return 0;
}