首页 > 试题广场 >

All-in-All

[编程题]All-in-All
  • 热度指数:557 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有两个字符串s 和t,如果即从s 中删除一些字符,将剩余的字符连接起来,即可获得t。则称t是s 的子序列。
请你开发一个程序,判断t是否是s的子序列。

输入描述:
输入包含多组数据,每组数据包含两个字符串s和t。

它们都由数字和字母组成,且长度小于100000。


输出描述:
对应每一组输入,如果t是s的子序列,则输出“Yes”;否则输出“No”。
示例1

输入

ABC ABC
ABC AB
ABC DE

输出

Yes
Yes
No
推荐
思路:定义两个字符串str1 和 str2,接收输入,然后定义两个循环变量i 和 j,令j = 0。从i = 0 ~ str1.length() - 1判断,如果str1[i] == str2[j],则 j ++, i ++;否则i ++,继续判断。直到i == str1.length()或j == str2.length(),退出循环。
    如果j == str2.length(), 即str2所有字符都可以在str1中顺序找到,输出“Yes”;否则输出“No”。
代码如下:
// write your code here cpp
#include <iostream>
#include <string>
using namespace std;
void jugeStr(string str1, string str2)
    {
    int len1 = str1.length(), len2 = str2.length();
    int i, j;  //定义str1和str2的循环变量
    for(i = 0, j = 0; i < len1 && j < len2;)
        {
        //如果str1[i] == str2[j],则移到str2的下一位
        if(str1[i] == str2[j])
            j ++;
        i ++;   //移到str1的下一位
    }
    if(j == len2)  //如果str2遍历完毕,表示str1中存在str2的所有字符
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
int main()
    {
    string s1, s2;
    while(cin >> s1 >> s2)
        jugeStr(s1, s2);
    return 0;
}
编辑于 2016-06-30 15:26:03 回复(0)
奇怪了,说输出为空,但是本地没有问题!!

#include<stdio.h>

#include<string>

#include<iostream>

using namespace std;

int main()

{

    string a,b;

    cin>>b;

    cin>>a;


    for(int i=0;i<b.size();i++)

    {

        if(a[0]==b[i])

        {

            for(int j=0;j<a.size();j++)

            {

                if(a[j]!=b[i+j]||i+j>=b.size())

                {

                    break;

                }

                cout<<"Yes"<<endl;

                return 0;

            }


        }

    }

    cout<<"No"<<endl;

    return 0;

}


发表于 2018-02-23 23:06:55 回复(0)

python solution

使用贪心算法。

import sys

for i in sys.stdin.readlines():
    str1, str2 = i.strip().split()
    for i in str1:
        if str2 and i == str2[0]:
            str2 = str2[1:]
    print("Yes" if not str2 else "No")
发表于 2017-11-16 18:23:44 回复(0)
#include <cstdio>
#include <limits.h>
#include <vector>
#include <functional>
#include <string>
#include <iostream>
using namespace std;
int main()
{
 //freopen("in.txt", "r", stdin);
 string s, t;
 while (cin >> s >> t)
 {
  if (s.size() < t.size())
  {
   cout << "No" << endl;
   continue;
  }
  int i = 0, j = 0;
  while (i < s.size() && j < t.size())
  {
   if (s[i] == t[j]) ++j;
   ++i;
  }
  cout << (j == t.size() ? "Yes" : "No") << endl;
 }
 return 0;
}

发表于 2017-07-27 12:13:31 回复(0)
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String s1=in.next();
			String s2=in.next();
			int len1=s1.length();
			int len2=s2.length();
			char[] cA1 = s1.toCharArray();
			char[] cA2 = s2.toCharArray();
			int i = 0, j = 0;
	        for(; i<len1 && j<len2;)
	        {
	            if(cA1[i] == cA2[j])
	            {
	                j++;
	            }
	            i++;
	        }
	         
	        if(j == len2)
	        {
	            System.out.println("Yes");
	        }
	        else
	        {
	            System.out.println("No");
	        }
		}
	}
}


发表于 2016-10-11 12:58:36 回复(0)
#include<cstdio>
(802)#include<cstring> 
int main(){
    char str1[100010],str2[100010];
    while(scanf("%s %s",str1,str2)!=EOF){
        int k=0;
        int len1=strlen(str1);
        int len2=strlen(str2);
        for(int i=0;i<len1&&k<len2;i++){
            if(str1[i]==str2[k])
            {
                 k++;
            }
        }
        if(k==len2){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

发表于 2020-03-14 22:52:45 回复(0)
暴力可以解决,两个变量i和j分别取循环主串s和子串t,相同都+1,不同就让i+(主串继续走).
#include <iostream>
#include <string.h>
using namespace std;
string allInAll(string s, string t) {
    int i = 0;
    int j = 0;
    int tLen = (int)t.length();
    
    while (s[i]&&t[j]) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i++;
        }
    }
    
    if (j == tLen) {
        return "Yes";
    } else {
        return "No";
    }
}
int main() {
    string s, t;
    while (cin>>s>>t) {
        cout<<allInAll(s, t)<<endl;
    }
    return 0;
}
发表于 2018-07-25 15:58:11 回复(0)
#include <stdio.h>
#include <string.h>

int main() {
    char a[100001], b[100001];
    while(scanf("%s%s", a, b) != EOF) {
        int i, j, lena = strlen(a), lenb = strlen(b);
        for(i = j = 0; i < lena && j < lenb; ++i) {
            if(a[i] == b[j]) {
                ++j;
            }
            if(j == lenb){
                printf("Yes\n");
                break;
            }
        }
        if(j < lenb)
            printf("No\n");
    }
    return 0;
}

发表于 2018-02-15 12:18:48 回复(0)
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string str, res;
	while (cin >> str >> res)
	{
		int j = 0;
		bool sta = false;
		for (auto c : str)
		{
			if (c == res[j])
				j++;
			if (j == res.length())
			{
				sta = true;
				break;
			}
		}
		
		if (sta == true)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

发表于 2017-04-23 18:45:59 回复(0)
// write your code here cpp
#include <iostream>
#include <string>
using namespace std;
int main()
{
    
    string s1,s2;
    while(cin>>s1>>s2)
    {
        
        int n=0;
        bool flag=0;
        for (int i=0;i<s2.length();i++)
        {
            
            for (int j=n;j<s1.length();j++)
            {
                
                if ((i==s2.length()-1)&&(s2[i]==s1[j]))
                {
                    
                    flag=1;
                    break;
                    
                }
                if (s2[i]==s1[j])
                {
                    
                    n=j+1;
                    break;
                    
                }
                
            }
            
        }
        if (flag==1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        
    }
    
}

发表于 2016-07-03 18:23:15 回复(1)
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner read = new Scanner(System.in);
		while(read.hasNext())
		{
			String str1 = read.next();
			String str2 = read.next();
			judgeStr(str1, str2);
		}
		read.close();
	}

	/**
	 * 
	 * @param source
	 * @param target
	 * @return
	 */
	public static int indexOf(char[] source, char[] target) {
		
		int targetCount = target.length;
		int sourceCount = source.length;
		
		if (targetCount == 0) {
			return 0;
		}

		char first = target[0];
		int max = sourceCount - targetCount;

		for (int i = 0; i <= max; i++) {
			if (source[i] != first) {
				while (++i <= max && source[i] != first)
					;
			}

			if (i <= max) {
				int j = i + 1;
				int end = j + targetCount - 1;
				for (int k = 1; j < end
						&& source[j] == target[k]; j++, k++)
					;

				if (j == end) {
					return i;
				}
			}
		}
		return -1;
	}
	
	public static void judgeStr(String str1, String str2)
	{
		int len1 = str1.length(), len2 = str2.length();
		
		int i = 0, j = 0;
		
		for(; i<len1 && j<len2;)
		{
			if(str1.charAt(i) == str2.charAt(j))
			{
				j ++;
			}
			i ++;
		}
		
		if(j == len2)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
	}
}

这个题的难点不是匹配,而是对题的理解,代码中第一个方法就是理解错了。最初理解成了全量匹配了,即:必须从某一位置开始,必须全部匹配才能算成功包含,而本题的意思为可以中断匹配,即“ABCDEF” “AE" 也是可以匹配成功的要成功输出Yes

发表于 2016-07-03 16:08:59 回复(0)