POJ-1936 All in All（字符串）

逃离我推掉我的手 2022-02-13 09:39 182阅读 0赞

**Problem Description:**

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.   
  
Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.

**Input:**

The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace.The length of s and t will no more than 100000.

**Output:**

For each test case output "Yes", if s is a subsequence of t,otherwise output "No".

**Sample Input:**

sequence subsequence
    person compression
    VERDI vivaVittorioEmanueleReDiItalia
    caseDoesMatter CaseDoesMatter

**Sample Output:**

Yes
    No
    Yes
    No

**题目大意：**

能不能在字符串t中删除一些字符得到s，能就输出Yes，不能就输出No。

**思路：**

先从字符串t中找到与字符串s的第一个字符相匹配的字符，然后再在字符串t中继续往后遍历，每找到一个匹配的字符s的假指针i就往后移一位，**最后判定一下i是不是到达了i是不是与lens（字符串s的长度）相等，如果相等则输出Yes，不相等则输出No。**

**上AC代码：**

#include <stdio.h>
    #include <string.h>
    char s[100001];
    char t[100001];
    int main()
    {
        int i,j,k;
        while(~scanf("%s %s",s,t))
        {
            int lens=strlen(s);
            int lent=strlen(t);
            bool res=false;
            //从s的第一个元素开始找
            i=0;
            for(j=0;j<lent;j++)
            {
                if(t[j]==s[i])
                {
                    //从s的第二个元素开始找
                    i++;
                    for(k=j+1;k<lent;k++)
                    {
                        if(t[k]==s[i])
                        {
                            i++;
                        }
                    }
                    if(i==lens)
                    {
                        res=true;
                    }
                    //一趟比较下来结果就出来了
                    break;
                }
            }
            if(res)
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
        return 0;
    }