北大 acm 3302 Subsequence 解题报告

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4753 Accepted: 2821

Description

Given a string s of length n, a subsequence of it, is defined as another string s’ = su1su2…sum where 1 ≤ u1 < u2 < … < um ≤ n and si is the ith character of s. Your task is to write a program that, given two strings s1 and s2, checks whether either s2 or its reverse is a subsequence of s1 or not.

Input

The first line of input contains an integer T, which is the number of test cases. Each of the next T lines contains two non-empty strings s1 and s2 (with length at most 100) consisted of only alpha-numeric characters and separated from each other by a single space.

Output

For each test case, your program must output “YES”, in a single line, if either s2 or its reverse is a subsequence of s1. Otherwise your program should write “NO”.

Sample Input

5arash aaharash hsrkick kkcA aa12340b b31

Sample Output

YESYESNONOYES

题意：两个字符串str1，str2，问str2是不是str1的子字符串，str2的顺序要么是str1从左到右要么从右到左 理解题意就简单了

代码

#include <iostream>

using namespace std;

void fan(char s[])
{
  int i,len=strlen(s);
  char t;

  for(i=0;i<len/2;i++)
  {
    t=s[i];
    s[i]=s[len-1-i];
    s[len-1-i]=t;
  }
}

int main()
{
  int n,i,len1,len2,k;
  char str1[105],str2[105];

  freopen("t.txt","rt",stdin);

  cin>>n;

  while(n--)
  {
    cin>>str1>>str2;   
    len1=strlen(str1);
    len2=strlen(str2);   
    k=0;   

    for(i=len1-1;i>=0;i--)
    {
      if(str2[k]==str1[i])
        k++;

      if(k==len2)
        break;
    }   

    if(k==len2)
    {
      cout<<"YES"<<endl;
      continue;
    }   

    fan(str1); //翻转字符串   k=0;

    for(i=len1-1;i>=0;i--)
    {
      if(str2[k]==str1[i])
        k++;

      if(k==len2)
        break;
    }

    if(k==len2)
    {
      cout<<"YES"<<endl;
      continue;
    }

    cout<<"NO"<<endl;
  }

  return 0;
}