突然有一天默默无闻的QAQ变成了FJUTOJ的终极大BOSS，而使得QAQ变强的是QAQ掌握有一个由小写字母组成魔咒。
作为QAQ小弟的V_Dragon偷偷的听到了一部分连续魔咒，V_Dragon非常的激动，因为这一部分魔咒能使得菜鸡V_Dragon
变强100倍。但V_Dragon的听力不是很好，有一些听不清，也有可能听错。但V_Dragon有个神奇的魔法，可以将他没听
清的部分变成QAQ魔咒中的任意部分（也可以为空）,现在要聪明的ACMer你来判断V_Dragon有没有听错。
（题目没看懂？ 没关系，看样例！！）
Input
输入包含多组测试数据
输入第一行表示QAQ掌握的魔咒，1<=s1<=100000,只包含小写字母
输入第二行表示V_Dragon偷听到的魔咒，1<=s2<=100000,'*'表示V_Dragon没听清的部分。只包含小写字母和'*'
Output
判断V_Dragon是否听错。没听错输出YES,听错输出NO
SampleInput
abcdef a*b*e abcdef a*c*f abcdef ac*f abc bc
SampleOutput
YES YES NO YES
提示： 样例1：第一个'*'表示一个空串，第二个'*'表示cd，变成abcde是魔咒的子串 样例2：第一个'*'表示b,第二个'*'表示de，变成abcdef是魔咒的子串 样例3：'*'不管代表什么都可能是魔咒的子串，所以V_Dragon肯定听错了 样例4：懒得解释
分析:在字符串2中，我们可以看成它是由*分割的几个字符串.如果要符合要求，那么这几个字符串就一定会按照顺序在串1中出现，
所以我们把这几个由*分割的字符串与串1进行KMP操作，找到它在串1中出现，并且满足先后顺序要求的第一个位置。
如果串2中所有的由*分割的字符串都能找到这样的位置 就输出 YES 否则输出NO
要特别注意的是 由单个和多个*号组成的串2 都输出YES
代码如下：
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N = 1000002; int Next[N]; char S[N], T[N]; char r[N]; int slen, tlen;//注意每次一定要计算长度 int rlen; int left1; int right1; void getNext() { int j, k; j = 0; k = -1; Next[0] = -1; while(j < tlen) if(k == -1 || T[j] == T[k]) Next[++j] = ++k; else k = Next[k]; } /* 返回模式串T在主串S中首次出现的位置 返回的位置是从0开始的。 */ int KMP_Index() { int i = 0, j = 0; getNext(); while(i < slen) { if(j == -1 || S[i] == T[j]) { i++; j++; } else j = Next[j]; if(j == tlen){ if(i-tlen>left1) return i - tlen; j=Next[tlen]; } } return -1; } int main() { int TT; int i, cc,cnt,flag; scanf("%d",&TT); while(scanf("%s",S)!=EOF) { flag=1; scanf("%s",r); slen = strlen(S); rlen=strlen(r); r[rlen]='*'; rlen++; r[rlen]=0; cnt=0; left1=-1; for(int i=0;i<rlen;i++) { if(r[i]!='*') { T[cnt++]=r[i]; continue; } else { if(cnt==0)continue; T[cnt]=0; tlen=cnt; right1=KMP_Index(); if(right1<=left1) { flag=0; break; } else{ left1=right1; cnt=0; } } } flag==1?puts("YES"):puts("NO"); } return 0; }