《算法竞赛入门经典（第2版）》习题3-9 子序列 (All in All, UVa 10340)

《算法竞赛入门经典（第2版）》习题3-9 子序列 (All in All, UVa 10340)

输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他顺序不变）， 得到字符串s。例如，abcde可以得到bce，但无法得到dc。 输入： 有若干行，每行包含两个字符串s和t，中间用空格分开，全部输入以EOF结束。 输出： Yes或No，表示是否可以由t得到s。

样例输入

sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter

样例输出

Yes No Yes No

分析

遍历s中的每一个字符，在t中寻找匹配，如果匹配，就在t的下一个位置继续开始匹配s中的下一个字符；如果不匹配，则继续在t中向后寻找此字符的匹配。如果t的字符都已经扫描过一遍，而s中的字符还没完成遍历，那么匹配失败，否则成功。

代码

#include <stdio.h> #include <string.h> #include <ctype.h> #include <time.h> char s[100000]; // 数组开小了将会WA，别问我是怎么知道的 char t[100000]; int main() { int i, j, ans=1; while((scanf("%s%s", s, t))!=EOF){ // 输入每一组字符串 for(i=0, j=0; i<strlen(s); i++){ // 检查s中的每一个字符是否都能够在t中找到匹配 if(j>=strlen(t)){ans=0; break;} // 如果s中的字符还没检查完，t已经扫描到头，说明匹配失败 else if(s[i]==t[j]) j++; // 匹配成功一个字符，两个下标都增1 else if(s[i]!=t[j]) {j++; i--;}// 某个字符没有找到，继续在t中寻找这个字符，i--退回，使下一次i++之后仍是这个字符 } if(ans==1 && i==strlen(s)) printf("Yes\n"); else printf("No\n"); memset(s, 0, 1000); // 清零 memset(t, 0, 1000); // 清零 ans = 1; // 还原 } return 0; }