HDU 5414 CRB and String （2015年多校比赛第10场）

2.解题思路：本题要求推断字符串s是否能通过加入若干个字符得到字符串t。

首先，能够知道，s必须是t的一个子串（注意：不是连续子串）。

第二。因为插入的新字符和它前面的字符c不同。因此假设t中有cnt个连续的c。那么在s中也必须有cnt个连续的c。因此。仅仅要能够满足这2个条件，就一定能够成功实现转化。

那么该怎样做呢？两者能够结合起来推断，用i,j分别表示s,t串中当前扫描的字符的下标。首先从字符串t開始扫描，看第一个字符c是否连续，一直到不连续为止，那么依据上述推断方法。i也应该在0~j-1中都是字符c。否则输出No。接下来。找到下一个t[j]和s[i]相等的位置，然后i,j同一时候前进。假设不相等。仅仅让j前进。假设发现j已经走到了终点，说明s不是t的子串，输出No。

3.代码：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;

#define me(s)  memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;


const int N=100000+5;
char s[N],t[N];

int n,m;
bool test()
{
    int i,j;
    for(j=1;j<n;j++)
        if(t[j]!=t[0])break;//找到第一个字符不连续的地方
    for(i=0;i<j;i++)     //对于i也应该在前j个字符都连续同样
        if(s[i]!=t[i])return 0;
    while(i<m)
    {
        for(;j<n;j++) //找到下一个和s[i]相等的地方
        if(t[j]==s[i])break;
        if(j==n)return 0;  //若j提前走到了终点，说明s不是t的子串。break
            i++,j++;  //两者齐头并进
    }
    return 1;
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;)
    {
        scanf("%s%s",s,t);
        m=strlen(s),n=strlen(t);
        puts(test()?"Yes":"No");
    }
}

HDU 5414 CRB and String （2015年多校比赛第10场）

推荐阅读