参考来源
https://blog.csdn.net/qq_38735931/article/details/89422093
题目
给你一个主字符串，最大长度为1e5
然后你n个字符串进行询问，n至多1e5，每个字符串最长为1e3
问你这个字符串是不是主字符串的子串（不必连续，但要按顺序）
思路
暴力明显超时。
先对主字符串做预处理，对于每一个字母，把改字母的位置存下来。
用一个vecter 的a[30], a[0]存字母a，a[1]存字母b…………
然后按着给出的子字符串查找字母，用
每次用二分查找（ upper_bound() ）
不理解的地方
这里的flag我原先是这样写的，不过在交的时候，有时A有时T
int flag=0;
…………………………
…………………………
int tem=ch[i]-'a';
if(a[tem].empty())
{
flag=1;
break;
}
…………………………
…………………………
…………………………
if(emm<a[tem].size()&&npos>pos)
pos=npos;
else
{
flag=1;
break;
}
…………………………
…………………………
if(flag)
NO();
else
YES();
换成下面代码那样就不会，而且时间短了至少半秒以上？不太清楚为什么。
这个算法复杂度是O(nmlogk),n*m的最大值是1e8，给出的字符串最多1e3，那log后小于3，相乘刚好小于3e8，而时间限制3s，(⊙o⊙)…在超时边缘疯狂试探。
代码
#include <bits/stdc++.h>
using namespace std;
char s[100005];
char ch[1005];
vector<int> a[30];
int main()
{
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<len;i++)
a[s[i]-'a'].push_back(i);
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",ch);
int ch_len=strlen(ch);
if(a[ch[0]-'a'].empty())
{
puts("NO");
continue;
}
int pos=a[ch[0]-'a'][0];
int flag=1;
for(int i=1;i<ch_len;i++)
{
int tem=ch[i]-'a';
if(a[tem].empty())
{
flag=0;
break;
}
int emm=upper_bound(a[tem].begin(),a[tem].end(),pos)-a[tem].begin();
if(emm<a[tem].size()&&a[tem][emm]>pos)
pos=a[tem][emm];
else
{
flag=0;
break;
}
}
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}
| 
转播
