2019 ICPC 南昌邀请赛网络赛 M题 Subsequence（预处理+二分查找）

104 阅读 0 评论 69 点赞

我是靠谱客的博主高大雨，这篇文章主要介绍2019 ICPC 南昌邀请赛网络赛 M题 Subsequence（预处理+二分查找），现在分享给大家，希望可以做个参考。

参考来源

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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⊙)…在超时边缘疯狂试探。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}