L: Long Long Ago
时间限制: 1 s 内存限制: 128 MB
题目描述
今天 SHIELD 捕获到一段从敌方基地发出的信息里面包含一串被经过某种算法加密过的的序列 L
组织的间谍活动如下几个线索:
这个算法不会改变秘密消息的字符顺序, 但是会两个字符之间在中间加入未知个数的字符
如原信息
ab
可能的加密结果
ammmxxxxb
现在你有 n 个待选关键字
如果这个关键字可能是秘密消息输出 Yes, 否则输出 No
如 ammmmxxxxb
可能包含的关键字有
- ab
- mb
- mxb
- ......
输入
第一行输入一串字符串 L
(1≤L≤105)
第二行输入一个整数 N, 表示查找字符串的个数.(1≤N≤105)
接下来 N 行表示, 输入一行字符串 M
n 个字符的长度之和为 [1,100000]
输出
输出 N
行, 如果是符合提议就输出 Yes, 否则输出 No
样例输入
- noiauwfaurainairtqltqlmomomo
- 8
- rain
- air
- tql
- ntt
- xiaobai
- oiiiooo
- orzcnzcnznb
- ooooo
样例输出
- Yes
- Yes
- Yes
- Yes
- No
- Yes
- No
- No
- #include<iostream>
- #include<math.h>
- #include<string.h>
- #include<vector>
- #define ll long long
- using namespace std;
- vector<ll>p[30];// 开个二维的动态数组
- char s[1000005],ss[1000005];
- ll find2(ll target, ll k)
- {
- if (p[target].size() == 0)
- return -1;
- else
- {
- ll l = 0, r = p[target].size() - 1, mid;
- while (l <= r)
- {
- mid = l + ((r - l)>> 1);
- if (p[target][mid]> k)//p[target][mid]=target 在 s 数组的下标
- r = mid - 1;
- else
- l = mid + 1;
- }
- if (l <= p[target].size()-1)
- return p[target][l];
- else
- return -1;
- }
- }
- int main()
- {
- ll n;
- scanf("%s", s);
- for (int i = 0;s[i]; i++)// 如果用 i<strlen(s) 会超时
- p[s[i] - 'a'].push_back(i);
- scanf("%lld", &n);
- while (n--)
- {
- scanf("%s", ss);
- ll k = -1, flag = 0;
- for (int i = 0; ss[i]; i++)
- {
- k=find2(ss[i] - 'a', k);//k 是上一次查找返回的位置, 初始化为 - 1
- if (k == -1)
- {
- flag = 1;
- break;
- }
- }
- if (flag == 0)
- printf("Yes\n");
- else
- printf("No\n");
- }
- //system("pause");
- return 0;
- }
超时的 strlen,sqrt
来源: http://www.bubuko.com/infodetail-3030626.html