pku3302结题报告

水题一个
题目要求:
给出两个字符串,s和sub
判断s是否包含了sub.包含是指s中含有sub的所有元素,并且在s中按照在sub的顺序或者逆序排列.
类似于串的模式匹配问题


#include <iostream>

using namespace std;

int main()
{
    char s[100];
    char sub[100];
    int t;
    int i=0,j=0,k=0;
    bool ok=1;
    int cur=0;
    cin>>t;
    for(k=0;k<t;k++)
    {
        cin>>s>>sub;
        int len1=strlen(s);
        int len2=strlen(sub);
        i=0;j=0;
        while(i<len1&&j<len2)
        {//正向查找
            if(s[i]==sub[j])//从头开始找,如果找到相同的字符,下标同时增加
            {
                i++;j++;
            }
            else  //否则,只增加s的下标
                i++;
        }
        if(j<len2)
            ok=0;
        else if(j==len2)//j==len2表示sub中的字符全部在s按顺序出现.输出"YES"后跳出本次循环
        {
            ok=1;
            cout<<"YES"<<endl;
            continue;
        }
        i=len1-1;j=0;//初始化下标
        while(i>=0&&j<len2)
        {//反向查找
            if(s[i]==sub[j])
            {
                i--;j++;
            }
            else
                i--;
        }
        if(j==len2)
        {//j==len2表示sub中的字符全部在s按顺序出现.输出"YES"后跳出本次循环
            ok=1;
            cout<<"YES"<<endl;
            continue;
        }
        cout<<"NO"<<endl;//所以查找都结束后仍然没有continue,说明未找到,输出"NO"
    }
//    system("PAUSE");
    return EXIT_SUCCESS;
}

评论