北大 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从左到右要么从右到左 理解题意就简单了

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}