1425. All in All

似乎不用dp还快一点。。

include

include

int main()
{
char s[100001],t[100001];
while(scanf(“%s %s”,s,t)!=EOF){
int ss=strlen(s),tt=strlen(t);
int i=0,j=0;
while(i<ss&&j<tt){
if(s[i]==t[j]) i++;
j++;
}
if(i==ss) printf(“Yes\n”);
else printf(“No\n”);
}
return 0;
}

这好像不是dp吧？还是说可以dp做？

//原始的暴力解法

include

include

include

include

using namespace std;
int main(){
//测试一个第一个字符串的顺序在第二个字符串有没有？？？
char s[100000],t[100000];
//string s,t;
//while(cin>>s>>t)
while(scanf(“%s %s”,s,t)!=EOF){
int len1=strlen(s);
int len2=strlen(t);
int flag=0;
int k=0;
for(int i=0;i<len1;i++){
for(int j=k;j<len2;j++){
if(s[i]==t[j]) { //上次匹对的j值 应该比本次的小
k=j+1;
flag++;
break;
}
}
if(flag==len1){
cout<<”Yes”<<endl;
break;
}
}

if(flag!=len1) cout<<"No"<<endl;

}
return 0;
}

写我的笨笨方法:

#include<iostream>
#include<string>
using namespace std;
int main(){
    string str1, str2;
    while(cin >> str1 >> str2){
        int i = 0, j = 0;
        while(i < str1.length() && j < str2.length()){
            if(str1[i] == str2[j])
                i++;
            j++;
        }

        if(i >= str1.length())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

}

include

include

include

using namespace std;

int main()
{
string s, t;
next:
while (cin >> s >> t)
{
int index = -1;
for (string::iterator c = s.begin(); c != s.end(); ++c)
{
index = t.find_first_of(*c, index + 1);
if (index == string::npos)
{
cout << “No” << endl;
goto next;
}
}
cout << “Yes” << endl;
}
return 0;
}

include\<iostream>

using namespace std;
string s, t;
int sl, tl;
int founded;
void dp(int spos, int tpos){
if(founded)return;
if(spos == sl){
founded = 1;
}
for(int i = tpos; i < tl; i++){
if(s[spos] == t[i]){
dp(spos + 1, i + 1);
}
}
return;
}
int main(){
while(cin >> s >> t){
founded = 0;
sl = s.length();
tl = t.length();
dp(0, 0);
if(founded){
cout << “Yes” << endl;
}
else{
cout << “No” << endl;
}
}
return 0;
}