紫书第三章课后习题--UVa10340

题目：UVa10340

 

地址：https://vjudge.net/problem/UVA-10340

 

题解：

给你俩字符串s1、s2，问你s2是否包含s1。

 

思路：

一开始写的代码写的是遍历s1每一个字符，在s2中进行寻找，记录在s2中的下标，并与上次得到的下标进行比较，判断是否比上次得到的下标来的小。

后来发现，在找s1的字符时，并不需要每次都遍历一遍s2，可以从上次查找到的位置的下一个开始查找。这样至多只要遍历一遍s2即可。

当然，由于数据量不是很大，所以不会超时，这两种方法都可以ac。

 

AC代码1：

#include<bits/stdc++.h>
using namespace std;

string s,t;

int main(){
    while(cin >> s >> t){
        int len1 = s.length();
        int len2 = t.length();
        int before = -1;
        int fail = 0;
        for(int i = 0;i < len1;++i){		///遍历s1的每一个字符 
                int flag = 0;
            for(int j = 0;j < len2;++j)			///在s2中进行查找 
                if(t[j]==s[i]&&j>before){		///如果能找到，并且此时的下标还比上次得到的下标还大 
                    flag = 1;
                    before = j;
                    break;
                }
                if(!flag){
                    fail = 1;
                    break;
                }
        }
        if(fail)    printf("No\n");				///输出 
        else printf("Yes\n");
    }
    return 0;
}

 

AC代码2：

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
using namespace std;

string s1,s2;

int main(){
    while(cin >> s1 >> s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int Index = 0;              ///记录目前已经遍历到s2的位置
        int i;
        for(i = 0;i < len1;++i){
            int Success = 0;         ///标记是否寻找成功
            while(Index<len2){
                if(s1[i]==s2[Index++]){
                    Success = 1;
                    break;
                }
            }
            if(!Success)
                break;
        }
        if(i < len1)                  ///输出
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}