首页 > 寻寻觅觅寻不到（T2）

Zxsoul

发表于 2021-09-10 22:39:58

【B.寻寻觅觅寻不到】题解看有位大佬写的题解挺长的，感觉这题目考察点就一个：区间字符串哈希对于区间的字符串哈希值，公式如下：题目也就是从字串中取出长度为的子串，将其放在主串的后面构成新的串，看是否和文本串匹配，这里指串。所以就是拼接的问题了，由于我们取了长度为的子串，那么整个主串展开全文

_Ariel

发表于 2021-09-11 08:09:28

知识点： hash 区间的值为：其中是进制。思路很显然，在串中枚举连续的个字符，放在后面，算一个值，然后再与串的值比较就好了。时间复杂度： code /* work by:Ariel_ Sorce:寻寻觅觅寻不到 Knowledge:hash Time:O(| 展开全文

白给怪

发表于 2021-09-11 10:30:15

想知道这题数据水还是C++ string的== 做的很好，这么暴力的做法跑起来竟然只要14ms #include<bits/stdc++.h> using namespace std; string M,C; int k; int main(){ ios::sync_wit 展开全文

5ab

发表于 2021-09-10 22:28:38

注意到不是很大，考虑枚举位置进行字符串哈希。枚举长为的子串，按照题意进行重组得到，与比较。显然直接对于每个位置哈希会超时，考虑预处理如下的哈希函数（是定值）：显然，如果，那么可以对哈希函数进行如下处理：所以对于，考虑：显然前后两者都可预处理，中间项直接暴力求解，复杂展开全文

陌研

发表于 2021-09-11 08:31:49

【B.寻寻觅觅寻不到】暴力，对于两个字符串a、b，如果a[pos]!=b[pos]，那么截取的k一定在pos处或者左边，枚举k就行了。特判有点麻烦。 #include <bits/stdc++.h> #define sz(x) (int)(x).size() using namespac 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛