【HDU-1358】Period【KMP的理解】

【HDU-1358】Period【KMP的理解】

问题链接:https://vjudge.net/problem/HDU-1358

Solution:

#include <iostream>
#include <string>

using namespace std;
// abcabcabc
// | | | | |
// v v v v v
// abcabc
//    abcabc
// 可以绘制每个字符的匹配线
// 如果长度与最大匹配差值小于最大匹配长度,则说明
// 前缀的一部分后缀已经成为了后缀的一部分前缀
// 如果此差值可以整除长度,则说明这个串是由这个差值串
// 多次拼接而成
const int LIM = 1e6 + 10;
int kmp[LIM];
string str;
void build() {
  int k = 0;
  kmp[0] = 0;
  for (int i = 1; i < str.size(); i++) {
    while (k > 0 && str[k] != str[i]) k = kmp[k - 1];
    if (str[k] == str[i]) k++;
    kmp[i] = k;
  }
}

void solution() {
  build();
  for (int i = 1; i < str.size(); i++) {
    int len = i + 1 - kmp[i];
    if (len != i + 1 && !((i + 1) % len))
      cout << i + 1 << ' ' << (i + 1) / len << "\n";
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  for (int k = 1; cin >> n && n; k++) {
    cout << "Test case #" << k << "\n";
    cin >> str;
    solution();
    cout << "\n";
  }
  return 0;
}