【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

代码:

#include <iostream>
#include <string>

using namespace std;

const int LIM = 1e5 + 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;
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
    cin >> n;
  while (n--) {
    cin >> str;
    build();
        int len = str.size();
        int l = len - kmp[str.size() - 1];
        if (l != len && !(len % l)) {
            cout << 0 << "\n";
        } else {
            cout << l - kmp[str.size() - 1] % l << "\n";
        }
    }
  return 0;
}

相关问题:【HDU-1358】Period【KMP的理解】