【题目描述】

【输入】

【输出】

【输入样例】

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)判断“两段字符串是否相等”的魔法。 显然，字符串哈希是最佳选择。

解题逻辑：

1. 提取前缀：长度为i的前缀，其实就是整个字符串从头开始截取i个字符。

2. 提取后缀：长度为i的后缀，就是整个字符串倒数i个字符，也就是区间[N-i+1,N]。

3. 把它们俩的哈希值抽出来，用==判断。相等就说明找到了一个答案，直接输出长度i。

三、 算法设计

核心在于构建一个靠谱的哈希提取黑盒。 为了避免边界越界和处理恶心的+1、-1偏移，强制将字符串转换为1-base（从下标1开始）。

1. 打表预处理基数幂： 声明一个p数组，预处理131的次方（131是常用的字符串哈希Base 值，能极大降低冲突率）。因为131的幂次是固定的数学结论，这部分放在while(cin>>s) 多组输入的外层，只算一次，榨干性能。

2. 前缀哈希数组构造：ans[i]=ans[i-1]*131+s[i-1]。这里s[i-1]是为了兼容C++ string底层的0索引。

3. 区间提取公式：封装gethash(l,r) 函数。闭区间[l,r] 的哈希值为：ans[r]-ans[l-1]*p[r-l+1]。

4. 线性扫描验证： 跑一个1到N的for循环，判断ans[i]==gethash(N-i+1,N)。

四、 时空复杂度分析

• 时间复杂度： 预处理P数组 O(M)（M 为最大长度400000）。对于每个输入的字符串，构造哈希数组耗时O(N)，一次遍历枚举长度O(N)，每次哈希比对O(1)。单次测试用例的时间复杂度为优秀的O(N)。

• 空间复杂度： 只开了两个长400010的unsigned long long数组，占用内存极小，空间复杂度O(N)。

五、 易错点总结

1. 多组输入： 题目明确说明“输入若干行”，必须使用while(cin>>s)。如果只读一次就会直接WA。

2. 自然溢出代替取模： 使用unsigned long long (ull) 让计算机在超过2^64−1时自动截断，相当于自动对2^64取模。千万不要再手动去%某个大质数，不仅拖慢运行速度，代码还容易写错。

3. I/O性能瓶颈： 字符串很长且测试数据多，建议在main刚开始加上 ios::sync_with_stdio(false); cin.tie(0);，否则容易被cin和cout卡常数导致超时。

4. 下标对齐： 前缀的末尾是i，后缀的起点是N−i+1。这两个坐标在草稿纸上画一下就能确认，切忌凭感觉乱写导致错位。

六、 完整代码

#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(l>r) return 0;
    return ans[r]-ans[l-1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //存储131的i次方（131为进制）
    p[0]=1;
    for(int i=1;i<=400005;i++) p[i]=p[i-1]*131;
    //多组输入
    while(cin>>s){
        //字符串长度
        int n=s.size();
        //存储s的前缀哈希（1-base）
        for(int i=1;i<=n;i++){
            ans[i]=ans[i-1]*131+s[i-1];
        }
        //从小到大枚举前缀/后缀的长度i
        //如果前缀跟后缀相同就输出
        for(int i=1;i<=n;i++){
            //如果前缀和后缀哈希值相等
            if(ans[i]==gethash(n-i+1,n)) cout<<i<<" ";
        }
        //当前字符串判断完之后换行
        cout<<"\n";
    }
    return 0;
}