CRB and String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 491 Accepted Submission(s): 186

Problem Description

CRB has two strings s and t.

In each step, CRB can select arbitrary character c of s and
insert any character d (d ≠ c)
just after it.

CRB wants to convert s to t.
But is it possible?

Input

There are multiple test cases. The first line of input contains an integer T,
indicating the number of test cases. For each test case there are two strings s and t,
one per line.

1 ≤ T ≤ 105

1 ≤ |s| ≤ |t| ≤ 105

All strings consist only of lowercase English letters.

The size of each input file will be less than 5MB.

Output

For each test case, output "Yes" if CRB can convert s to t, otherwise output "No".

Sample Input

4

a

b

cat

cats

do

do

apple

aapple

Sample Output

No

Yes

Yes

No

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

/* ***********************************************

Author        :CKboss

Created Time  :2015年08月21日 星期五 09时23分23秒

File Name     :HDOJ5414.cpp

************************************************ */

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstdlib>

#include <vector>

#include <queue>

#include <set>

#include <map>

using namespace std;

const int maxn=100100;

int n,m;

int pip[maxn];

char S[maxn],T[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T_T;

    scanf("%d",&T_T);

    while(T_T--)

    {

        scanf("%s",S);

        scanf("%s",T);

        n=strlen(S); m=strlen(T);

        if(n>m) { puts("No"); }

        else if(n==m)

        {

            if(strcmp(S,T)==0) puts("Yes");

            else puts("No");

        }

        else

        {

            T[m]='&';

            bool flag=true;

			if(S[0]!=T[0]) flag=false;

            for(int i=0;i<n&&flag;i++)

            {

                bool temp=false;

                int st=0;

                if(i) st=pip[i-1]+1;

                for(int j=st;j<m;j++)

                {

                    if(S[i]==T[j]&&S[i]!=T[j+1])

                    {

                        /// find a point

                        pip[i]=j;

                        /// go back

                        int ni=i+1;

                        int ed=0;

                        if(i) ed=pip[i-1]+1;

                        for(int k=pip[i]-1;k>=ed;k--)

                        {

                            if(T[k]==S[ni])

			    {

				pip[ni]=pip[i];

				ni++;

			    }

                            else break;

                        }

                        i=ni-1;

                        temp=true; break;

                    }

                }

                if(temp==false) flag=false;

            }

            /// spc judge start point

            if(pip[0]!=0&&flag)

            {

                int len=1;

                for(int i=1;i<n;i++)

                {

                    if(S[i]==S[0]&&pip[0]==pip[i]&&len<pip[0]+1) len++;

                    else break;

                }

            	if(len!=pip[0]+1) flag=false;

            }

            if(flag==true) puts("Yes");

            else puts("No");

        }

    }

    return 0;

}

CRB

HDOJ 5414 CRB and String 模拟

CRB and String