Subsequence

Subsequence

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 29   Accepted Submission(s) : 18

Problem Description

Given a string s of length n, a subsequence of it, is defined as another string s' = s_u1s_u2...s_um where 1 ≤ u₁ < u₂ < ... < u_m ≤ n and s_i 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

5 arash aah arash hsr kick kkc A a a12340b b31

 

Sample Output

YES YES NO NO YES

 

Source

PKU

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int T,i,j,k,len,sign,num1,num2;
    char a[10000];
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        gets(a);
        len=strlen(a);
        for(i=0;i<len;i++)
            if(a[i]==' ')
            {sign=i;break;}
        for(j=0,i=sign+1,k=len-1,num1=1,num2=1;j<sign&&i<len;j++)
        {
            if(a[i]==a[j])
                {num1++;i++;}
            if(a[k]==a[j])
                {num2++;k--;}
        }
        if(num1==len-sign||num2==len-sign)
            printf("YES
");
        else
            printf("NO
");
    }
    return 0;
}