Seek the Name, Seek the Fame（信息学奥赛一本通- P1458）

【题目描述】原题来自POJ 2752给定若干字符串这些字符串总长 ≤4×10^5​​ 在每个字符串中求出所有既是前缀又是后缀的子串长度。例如ababcababababcabab既是前缀又是后缀的abababababcababababcababababcabab。【输入】输入若干行每行一个字符串。【输出】对于每个字符串输出一行包含若干个递增的整数表示所有既是前缀又是后缀的子串长度。【输入样例】ababcababababcabab aaaaa【输出样例】2 4 9 18 1 2 3 4 5今天来一道经典的字符串匹配题POJ 2752 (Seek the Name, Seek the Fame)。这道题在算法教材里通常是被当做 KMP 算法的引申例题来讲的但是如果实战中碰到用字符串哈希直接平推不仅思维极其直观代码写起来也更不容易翻车。下面把这道题的拆解过程记录下来。一、 题目分析题意给出一个长度不超过 400,000 的字符串 S要求找出所有既是 S 的前缀、又是 S 的后缀的子串并按长度从小到大输出这些子串的长度。样例ababcababababcabab肉眼可见的答案ab(长度2),abab(长度4) ...一直到整个字符串本身。二、 思考过程与解题思路看到“前缀等于后缀”最暴力的想法就是枚举长度i然后用两个for循环或substr去切字符串对比。但看一眼数据范围字符串总长4×10^5并且有多组测试数据。暴力截取比对的时间复杂度是O(N2)稳稳超时。我们需要一种O(1)判断“两段字符串是否相等”的魔法。 显然字符串哈希是最佳选择。解题逻辑提取前缀长度为i的前缀其实就是整个字符串从头开始截取i个字符。提取后缀长度为i的后缀就是整个字符串倒数i个字符也就是区间[N-i1,N]。把它们俩的哈希值抽出来用判断。相等就说明找到了一个答案直接输出长度i。三、 算法设计核心在于构建一个靠谱的哈希提取黑盒。 为了避免边界越界和处理恶心的1、-1偏移强制将字符串转换为1-base从下标1开始。打表预处理基数幂声明一个p数组预处理131的次方131是常用的字符串哈希Base 值能极大降低冲突率。因为131的幂次是固定的数学结论这部分放在while(cins)多组输入的外层只算一次榨干性能。前缀哈希数组构造ans[i]ans[i-1]*131s[i-1]。这里s[i-1]是为了兼容Cstring底层的0索引。区间提取公式封装gethash(l,r)函数。闭区间[l,r]的哈希值为ans[r]-ans[l-1]*p[r-l1]。线性扫描验证跑一个1到N的for循环判断ans[i]gethash(N-i1,N)。四、 时空复杂度分析时间复杂度预处理P数组 O(M)M 为最大长度400000。对于每个输入的字符串构造哈希数组耗时O(N)一次遍历枚举长度O(N)每次哈希比对O(1)。单次测试用例的时间复杂度为优秀的O(N)。空间复杂度只开了两个长400010的unsigned long long数组占用内存极小空间复杂度O(N)。五、 易错点总结多组输入题目明确说明“输入若干行”必须使用while(cins)。如果只读一次就会直接WA。自然溢出代替取模使用unsigned long long(ull) 让计算机在超过2^64−1时自动截断相当于自动对2^64取模。千万不要再手动去%某个大质数不仅拖慢运行速度代码还容易写错。I/O性能瓶颈字符串很长且测试数据多建议在main刚开始加上ios::sync_with_stdio(false); cin.tie(0);否则容易被cin和cout卡常数导致超时。下标对齐前缀的末尾是i后缀的起点是N−i1。这两个坐标在草稿纸上画一下就能确认切忌凭感觉乱写导致错位。六、 完整代码#include iostream using namespace std; //ull会自动溢出 省去取模操作 typedef unsigned long long ull; string s; ull ans[400010];//存储字符串的前缀哈希(1-base) ull p[400010];//存储进制131的i次方 //返回闭区间[l,r]的哈希值 ull gethash(int l,int r){ if(lr) return 0; return ans[r]-ans[l-1]*p[r-l1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); //存储131的i次方131为进制 p[0]1; for(int i1;i400005;i) p[i]p[i-1]*131; //多组输入 while(cins){ //字符串长度 int ns.size(); //存储s的前缀哈希1-base for(int i1;in;i){ ans[i]ans[i-1]*131s[i-1]; } //从小到大枚举前缀/后缀的长度i //如果前缀跟后缀相同就输出 for(int i1;in;i){ //如果前缀和后缀哈希值相等 if(ans[i]gethash(n-i1,n)) couti ; } //当前字符串判断完之后换行 cout\n; } return 0; }