KMP（4）

例 6 题目链接：POJ2752

这道题目的大意是给定一个字符串 S，让找出所有既是 S 前缀又是 S 后缀的字符串。然后从小到大输出它们的长度

比如 S=ababcababababcabab，既是前缀又是后缀的有 ab, abab, ababcabab 和 S 本身。所以输出的是 2 4 9 18。再比如 S=aaaaa，既是前缀又是后缀的有 a, aa, aaa, aaaa 和 S 本身。所以输出的是 1 2 3 4 5

next 数组的定义是：如果 P [1..k] 是 P [1..j] 的最长的满足 “既是前缀也是后缀” 的字符串，那么 next [j]=k。并且 P [1..j] 的所有满足 “既是前缀也是后缀” 的字符串都通过 next 数组的连线连在一起。比如满足既是 babab 前缀又是 babab 后缀的字符串有 bab 和 b，对应 next [5]=3 和 next [3]=1

所以这道题的解法就是把输入的字符串当作 P，求出 P 的 next 数组，则 {m, next [m], next [next [m]], … } 反转一下顺序就是答案

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int nxt[1000001];
int m,t;
char p[1000001];
vector<int> ans;
int main()
{
    while(scanf("%s",p + 1) != EOF)
    {
        ans.clear();
        m = strlen(p + 1);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        while(m)
        {
            ans.push_back(m);
            m = nxt[m];
        }
        reverse(ans.begin(),ans.end());
        for(int i = 0;i < ans.size();i++)
        {
            cout << ans[i];
            if(i == ans.size() - 1)
                cout << endl;
            else
                cout << " ";
        }
    }
    return 0;
}

例 7 题目链接：POJ2406

这道题的大意是：对于一个字符串 S，我们把 S 重复 K 次得到的字符串记作 S^K。比如 (ab)^3=ababab，(abc)^2=abcabc， abcd^1=abcd。现在给定一个字符串 S，让你求出最大的整数 K，使得 S 能表示成一个字符串的 K 次方

例如对于 S=abcd，就只能表示成 abcd^1；S=aaaa 就能表示成 a^4；S=ababab 就能表示成 ab^3

这类同字符串循环节有关的题目是 next 数组的经典应用场景。首先我们来看一个定理：字符串 P 是由 t 个字符循环 K 次组成的，当且仅当 P.len = t * K 且 P [1..P.len-t] 是 P 的后缀。我们看一下下图中的几个例子应该就比较清楚了

需要注意的是，如果只有 “P [1..P.len-t] 是 P 的后缀 “这一个条件，P 不一定是 t 个字符循环的。例如”abcdab “是” abcdabcdab” 的后缀，但是”abcdabcdab” 并不是 t=4 个字符循环的

有了这个定理，我们再求解上面的问题就简单多了。对于输入的字符串 P，假设 P 的长度是 m。我们知道满足 P [1..j] 是 P 的后缀的整数 j，都在 next [m], next [next [m]]…… 这条链上。所以我们可以依次遍历这条链上的每一个整数 x，再判断 m-x 是不是 m 约数，这里 m-x 就是循环节长度 t。最后找一个 m-x 是 m 约数的最大的 x，m/(m-x) 即是答案

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int m,x,ans;
char p[1000001];
int main()
{
    scanf("%s",p + 1);
    while(strcmp(p + 1,".") != 0)
    {
        m = strlen(p + 1);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        x = nxt[m];
        while(x != -1)
        {
            if(m % (m - x) == 0)
            {
                ans = m - x;
                break;
            }
            x = nxt[x];
        }
        cout << m / ans << endl;
        scanf("%s",p + 1);
    }
    return 0;
}

例 8 题目链接：HUSTOJ1010

这道题的大意就是给定一个字符串 S，让你找到 S 的最短的循环节。这里循环次数可以不是整数，例如 abcd 循环 2.25 次是 abcdabcda，bca 循环 2 (1/3) 是 bcabcab，efgacbd 循环 2 (1/7) 是 efgabcdefgabcde

这道题和之前一题很类似，区别就是允许最后一段是残缺的，可以不是完整的循环。之前那道题我们有个定理：字符串 P 是由 t 个字符循环 K 次组成的，当且仅当 P.len = t * K 且 P [1..P.len-t] 是 P 的后缀。这道题不要求完整循环 K 次，其实等价于不需要 P.len 是 t 的倍数。所以我们求出 next 数组之后，m-next [m] 就是答案

例 9 题目链接：POJ2185

这道题的大意是给一个 R*C 的二维字符矩阵 A，然后让你找到一个面积最小的二维矩阵 B，满足 B 循环铺开若干次之后就能得到 A

注意本题中循环铺开也不需要完整循环。例如

ABABA
ABABA

就可以看作是 AB 在 X 方向上循环了 2.5 次，在 Y 方向上循环了 2 次得到的

这道题也是找循环节，允许循环不完整。但是与之前的题目最大的区别是这道题是二维的。解决这道题的关键是意识到二维矩阵的循环实际上在 2 个维度上是独立的，可以分别计算

比如我们先处理 X 方向上的循环节，就可以把矩阵的每一列看成一个 “字符 “，只不过这个” 字符 “实际上是一个字符 R 元组。这样整个矩阵就可以看成是包含 C 个” 字符 “的” 字符串 “。然后我们求这个” 字符串 “的循环节就可以得到 X 方向的循环节长度。当然在这种情况下，比较两个” 字符 “相等的方法是比较两个 R 元组是不是完全相等

对于 Y 方向的循环节也可以用类似的方法：把一行 C 元组看成一个 “字符 “，然后在 R 个” 字符 “的字符串上找循环节。最后两维的循环节长度相乘就是答案

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int n,m,x,ans;
char p[10001][80];
bool samec(int i,int j)
{
    for(int k = 1;k <= n;k++)
        if(p[k][i] != p[k][j])
            return false;
    return true;
}
bool samer(int i,int j)
{
    for(int k = 1;k <= m;k++)
        if(p[i][k] != p[j][k])
            return false;
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
        scanf("%s",&p[i][1]); 
    nxt[0] = -1;
    int j = -1;
    for(int i = 1;i <= m;i++)
    {
        while(j >= 0 && !samec(j + 1,i))
            j = nxt[j];
        nxt[i] = ++j;
    }
    ans = m - nxt[m];
    j = -1;
    for(int i = 1;i <= n;i++)
    {
        while(j >= 0 && !samer(j + 1,i))
            j = nxt[j];
        nxt[i] = ++j;
    }    
    ans *= n - nxt[n];
    cout << ans << endl;
    return 0;
}

上面代码第 28~35 是在求 X 方向的循环节，第 37~43 是在求 Y 方向的循环节。最后 (m-nxt [m])*(n-nxt [n]) 就是答案。注意第 32 行和 40 行，原本在求 next 数组的比较是 p [j+1] != p [i]，因为这里要比较的是 R 元组或 C 元组，所以我们用了！samec (j+1, i) 和！samer (j+1, i) 进行比较