Uva 1328 KMP乱杀循环节问题

一、题意

每组数据第一行一个n,第二行给一个长度为n的字符串。
要求列出所有的(i, k)满足该字符串的前i个字符组成的前缀子串是由k个子串循环而成的。

二、解析

中心问题就是求出某个字符串的循环节。
求循环节应该马上想到KMP算法。
求出Next数组后，根据Next数组的定义，Next[i]=j表示j为s[i]匹配失败后需要跳回的位置，也即是i和j之前可能为相同的串。对于一个循环串来说，它的Next数组“跳回”的长度正好就是一个循环节。因此通过i-Next[i]即可计算出s[1..i)的循环节长度，但注意可能字符串不是循环字符串，因此还要判定字符串长度i是否能被循环节长度i-Next[i]整除。

三、代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 1000000 + 5;
int n, Next[maxn], kase = 1;
string str;

void getNext(string& p, int m) {
    Next[0] = -1;
    int i = 0, j = -1;
    while(i < m) {
        if(j == -1 || p[i] == p[j]) i ++, j ++, Next[i] = j;
        else j = Next[j];
    }
}

int main() {
    while(cin >> n && n) {
        cout << "Test case #" << kase ++ << "\n";
        cin >> str;
        getNext(str, n);
        for(int i = 2; i <= n; i ++) {
            if(Next[i] && i % (i - Next[i]) == 0) cout << i << " " << i / (i - Next[i]) << "\n";
        }
        cout << endl;
    }
}

四、归纳

• KMP算法要牢记！！虽然这里只用了getNext数组的求法，但完整的算法也应该记住。

    int KMP(const string& t, int n, const string& p, int m, int* Next) {
    // 直接返回第一次匹配的写法
    int i = 0, j = 0;
    while(i < n && j < m) {
        if(j == -1 || t[i] == p[j]) i ++, j ++;
        else j = Next[j];
    }
    if(j == m) return i - j;
    return -1;
  }
  int KMP(const string& t, int n, const string& p, int m, int* Next) {
    // 返回匹配次数的写法
    int i = 0, j = 0;
    while(i < n) {
        if(j == -1 || t[i] == p[j]) i ++, j ++;
        else j = Next[j];
        if(j == m) cnt ++, j = Next[j];
    }
    return cnt;
  }
  void getNext(string& p, int m) {
    Next[0] = -1;
    int i = 0, j = -1;
    while(i < m) {
        if(j == -1 || p[i] == p[j]) i ++, j ++, Next[i] = j;
        else j = Next[j];
    }
  }

• 要注意KMP算法与循环节的关系
• 要理解清楚Next数组的含义：Next数组是针对匹配串（短串）的；比如abac，Next[3]=1，表示c匹配失败后会跳到b的位置进行下一次匹配，这样就节省了重复匹配a的时间。

加油！只剩半个月不到了