数据结构（七）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 全在其中 ——

1.题目描述

你设计了一个新的加密技术，可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题，我们将不会详细讨论如何在原有信息中产生和插入字符串。不过，为了验证你的方法，有必要写一个程序来验证原来的信息是否全在最后的字符串之中。

给定两个字符串s和t，你需要判断s是否是t的“子列”。也就是说，如果你去掉t中的某些字符，剩下字符将连接而成为s。

1.1输入

输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000。

1.2输出

对于每个测试样例，如果s是t的“子列”，则输出”Yes”，否则输出”No”

1.3样例输入与输出

样例输入
sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter
样例输出
Yes
No
Yes
No

2.代码实现

c

#include<stdio.h>
#include<string.h>

int main()
{
    char str_s[100001],str_t[100001];
    while(scanf("%s %s",str_s,str_t) != EOF)
    {
        int length_s=strlen(str_s),length_t=strlen(str_t),num=0,strlong=0;
        for(int i=0;i<length_s;++i)
        {
            if(num==length_t)
                break;
            for(;num<length_t;num++)
            {
                if(str_s[i]==str_t[num])
                {
                    strlong++;
                    num++;
                    break;
                }
            }
        }
        if(strlong==length_s)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

c++

#include<cstdio>
#include<cstring>
using namespace std;
char str_s[100001],str_t[100001];
bool judge(char * s, char * t){
    while(*s != '\0' && *t != '\0'){
        while(*t != *s){
            t++;
            if(*t == '\0') return false;
        }
        s++,t++;
    }
    return *s == '\0';
}
int main(){
    while(scanf("%s%s",str_s,str_t) != EOF){
        if(strlen(str_s) > strlen(str_t)) puts("No");
        else if(judge(str_s,str_t)) puts("Yes");
        else puts("No");
    }
    return 0;
}

3.代码说明

这道题的基本思路就是将字符串s的每个字符与字符串t的每个字符进行对比，需要注意的是在s中的一个字符对比结束后，若在t中有相同的字符，则s中下一个字符比对从该字符的位置开始；若在t中没有相同的字符，则直接输出“No”。