【每日一题】 4-2 月月查华华的手机
题意：
给一个长度为 1e6 的串，多次判断一个串是否是这个串的子串
做法：
显然直接暴力会超时，我们可以考虑在主串中判断子串的过程，实际上就是在主串当前位置之后找到一个等于子串当前位置的字符，这一过程显然是可以预处理的，所以我们预处理从每个位置开始，在他后面的离他最近的各个字母的位置，这样每次查询的时候，知找子串在主串中下一个匹配的位置，同时向后移一位即可，主串中没有子串匹配的位置，那么输出No，否则Yes，所以对于每次询问只需要查询子串的长度次，时间复杂度 )
代码:
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int dp[1000005][26];
char s[1000005];
char s1[1000005];
int main()
{
sc("%s", s + 1);
int sz = strlen(s + 1);
for (int i = sz; i >= 1; i--)
{
for (int j = 0; j < 26; j++)
dp[i][j] = dp[i + 1][j];
dp[i][s[i] - 'a'] = i;
}
int T;
sc("%d", &T);
while (T--)
{
sc("%s", s1 + 1);
int len = strlen(s1 + 1);
int ans = 1;
for (int i = 1; i <= len; i++)
{
ans = dp[ans][s1[i] - 'a'] + 1;
if (ans == 1)
{
pr("No\n");
goto qwe;
}
}
pr("Yes\n");
qwe:;
}
} 
投递中国南方电网等公司10个岗位 >
大疆公司氛围 166人发布