本文主要是介绍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 <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;
}
这篇关于CF - 223 - B. Two Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
