【题目描述】给出两个字符串s1,s2(只有大写字母求s1在s2中出现多少次。例如s1ABA,s2ABAABA,答案为2。【输入】输入T组数据每组数据输出结果。【输出】如题述。【输入样例】3 BAPC BAPC AZA AZAAZAAZA VEEDI AVERDXIVYERDLAN【输出样例】1 3 0【提示】1≤s1的长度 ≤10^4​​ 1≤s2的长度 ≤10^6​ 。今天来做一道经典的字符串匹配题Oulipo。题目要求在长度为10^6的文本串S2​中寻找长度为 10^4的模式串S1​出现的次数。一提到字符串匹配很多人第一反应是KMP算法。但KMP的next数组确实有点烧脑容易写挂。相比之下字符串哈希思维负担更小代码也更短是日常刷题和打比赛的利器。在这道题的调试过程中有一个极其经典的“精度天坑”特此把思考过程和避坑指南记录下来希望能帮到同学们。一、 题目分析与思考过程常规的暴力查找两层for循环滑动窗口时间复杂度是O(N×M)。代入题目的数据范围 10^4×10^610^10丢给评测机绝对是妥妥的超时。我们需要一个O(NM)级别的算法。 既然逐个字符比较太慢那能不能把一整段字符串变成一个数字只要算出来的数字相等我们就认为字符串相等。比较两个数字是否相等是O(1)的操作这就是哈希的初衷。二、 算法设计前缀哈希自然溢出进制选择BASE把字符串看成一个“大进制数”。为了避免和ASCII码产生冲突进制基数一般选一个大于127的质数这里综合考虑采用常用的经验值131。取模策略因为字符串可能很长算出来的数字会极其巨大必须取模。这里用到了 C 的黑科技声明类型为unsigned long long简写为ull。当数值超过2^64−1 时它会自动舍弃高位绕回这在数学上等价于对2^64自动取模免去了频繁写%的繁琐和耗时。区间哈希提取 维护一个前缀哈希数组ans2[]。如果我们想截取某一段长度为len的子串可以利用公式在O(1)时间内求出Hash(区间)右端点前缀−(左侧多余前缀×131^len)三、 时空复杂度分析时间复杂度计算S1​哈希值 O(N)预处理 S2​ 前缀哈希 O(M)滑动窗口每次查询 O(1)共滑动 M−N1 次。整体时间复杂度 O(NM)完全可以1s内跑完。空间复杂度需要开辟一个大小为10^6的ans2数组以及一个存进制幂次的p数组空间复杂度O(M)满足65536KB的内存限制。四、 避坑指南千万别在哈希里用 pow()在部分同学代码中在滑动窗口提取哈希值时写出了这样的代码sumans2[i]-ans2[i-len1]*pow(131, len1);下面我演示一下这位同学的思路和全部代码思路其实很容易理解很清晰但是一提交就会WA。//这种做法最后会产生问题因为pow返回浮点类型 ull减去浮点类型会出错 所以我们要把131的次方全部存入一个数组 //这道题要把进制设置的足够大可以包含所有字符所以应大于最大的ascii //再设置为一个素数综合考虑设置为131 //然后因为值过大所以要取余 我们可以用unsigned long long自动截断 #include iostream #include algorithm #include cmath #include vector using namespace std; typedef unsigned long long ull; string s1; string s2; ull ans1;//记录s1的哈希值 ull ans2[1000010];//记录s2每一位的哈希值 int main(){ int t; cint; while(t--){ int cnt0;//记录s1在s2中出现多少次 ans10;//初始化ans1 cins1s2; //s1的长度 int len1s1.size(); //s2的长度 int len2s2.size(); //如果s1长度大于s2长度 //s2不可能包含s1 输出0然后跳过本轮循环 if(len1len2){ cout0\n; continue; } //先计算出s1的哈希值 for(int i0;is1.size();i){ ans1ans1*131s1[i]; } //计算出s2的哈希值的前缀和 for(int i0;is2.size();i){ if(i0) ans2[i]s2[i]; else{ ans2[i]ans2[i-1]*131s2[i]; } } //最后窗口滑动计算有多少个窗口内的哈希值和s1哈希值相等 for(int ilen1-1;is2.size();i){ ull sum0; //窗口位于最左端时 特判 if(ilen1-1){ sumans2[i]; if(sumans1) cnt; } else{ sumans2[i]-ans2[i-len1]*pow(131,len1); if(sumans1) cnt; } } coutcnt\n; } return 0; }交上去直接 WA答案错误甚至部分数据超时。罪魁祸首就是cmath库里的pow()函数。为什么不能用pow()精度丢失pow()的返回值是double浮点型。当计算 13110000 时这个数字早就超出了double的精确表示范围变成了科学计数法的近似值。破坏取模机制用ull去减去一个丢失精度的double会发生隐式类型转换底层二进制全乱套了我们依赖的“自动取模截断”魔法直接失效。卡常数pow()内部实现复杂每次循环调一次在百万级数据下极其耗时。正确做法预处理打表。开一个ull p[]数组在最开始把131的次方全部算好存进去。全程保持纯ull整数运算完美避开浮点数精度坑。五、 完整正确代码下面是经过优化的 AC 代码注意看里面的小细节我把预处理次方的循环提到了while(t--)外面多组数据只算一次进一步压缩了运行时间。//这道题要把进制设置的足够大可以包含所有字符所以应大于最大的ascii //再设置为一个素数综合考虑设置为131 //然后因为值过大所以要取余 我们可以用unsigned long long自动截断 #include iostream #include algorithm #include vector using namespace std; //ull自动截断等价于对2^64取模 typedef unsigned long long ull; string s1; string s2; ull ans1;//记录s1的哈希值 ull ans2[1000010];//记录s2每一位的前缀哈希值 ull p[10010];//预处理 记录131的i次方 int main(){ ios::sync_with_stdio(false); cin.tie(0); //预处理打表131的次幂替代pow() //放在while外面多组测试数据只需算一次 p[0]1; for(int i1;i10005;i) p[i]131*p[i-1]; int t; cint; while(t--){ int cnt0;//记录s1在s2中出现多少次 ans10;//初始化ans1 cins1s2; //s1的长度 int len1s1.size(); //s2的长度 int len2s2.size(); //如果s1长度大于s2长度 //s2不可能包含s1 输出0然后跳过本轮循环 if(len1len2){ cout0\n; continue; } //先计算出s1的哈希值 for(int i0;is1.size();i){ ans1ans1*131s1[i]; } //计算出s2的哈希值的前缀和 for(int i0;is2.size();i){ if(i0) ans2[i]s2[i]; else{ ans2[i]ans2[i-1]*131s2[i]; } } //最后窗口滑动计算有多少个窗口内的哈希值和s1哈希值相等 //窗口右端点i从len1-1开始确保框住的长度刚好是len1 for(int ilen1-1;is2.size();i){ ull sum0; //窗口位于最左端时 特判 前面没有多余的前缀需要减去 if(ilen1-1){ sumans2[i]; if(sumans1) cnt; } else{ //核心区间哈希提取公式当前前缀-(多余前缀*权重) //使用查表p[len1]代替pow() sumans2[i]-ans2[i-len1]*p[len1]; if(sumans1) cnt; } } coutcnt\n; } return 0; }最后总结一句写哈希题老老实实开个数组打表算次幂远离一切浮点函数保平安。