题目:月月查看华华的手机 思路:此题根据A的长度一看如果暴力两次循环的话,会出现时间过长的情况;因此需要换个思路来减少时间复杂度;我是通过建立一个二维数组a[i][j]来存A中第i个位置以后j字母出现的位置;然后读入小姐姐的昵称并对其昵称进行遍历来看a中是否有;
代码:
#include<iostream>
#include<string.h>
using namespace std;
string a;
int n;
int s[1000010][40 用来存A中第i个位置以后j字母出现的位置
int main(){
memset(s, 0, sizeof(a));
cin>>a;
int l = a.length();
for (int i = l-1; i >= 0; i--) //逆着遍历去看每个位置的字母j的位置
{
for(int j=0;j<26;j++)
s[i][j] = s[i+1][j]; //第i个位置应该继承i+1个位置的数据
s[i][a[i]-'a']=i+1; //第i个位置仅有它本身的字母a[i]的位置要更新
}
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
string s1;
cin>>s1;
int l1 = s1.length();
bool flag = 1;
int k=0;
for (int j = 0; j < l1; j++)
{
if(s[k][s1[j]-'a'])k=s[k][s1[j]-'a'];
else
{
flag=0;
break;
}
}
if (flag)printf("Yes\n");
else printf("No\n");
}
return 0;
}**