题意:给出两个由小写字母组成的字符串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 <cstdio> #include <cstring> 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; }