1
class Solution {
2
 public:
3
  vector<int> get_kmp_table(const string &s) {
4
    vector<int> table(s.size());
5
    int i = 0;
6
    int j = -1;
7
    table[0] = -1;
8
    while (i < s.size()) {
9
      if (j == -1 || s[i] == s[j]) {
10
        i++;
11
        j++;
12
        table[i] = j;
13
      } else {
14
        j = table[j];
15
      }
16
    }
17
    return table;
18
  }
19

20
  bool validate_table(const vector<int> &table) {
21
    int idx = table.size() - 1;
22
    while (idx >= 0 && table[idx] > 0) {
23
      idx--;
24
    }
25
    if (idx <= 0) return false;
26
    int substr_len = idx;
27
    if (table.size() % substr_len != 0) return false;
28
    idx = idx + 1; // the first nonzero element in the string
29
    while (idx < table.size() - 1) {
30
      if (table[idx] != table[idx + 1] - 1) return false;
31
      idx++;
32
    }
33
    return true;
34
  }
35

36
  bool repeatedSubstringPattern(string s) {
37
    if (s.size() <= 1) return true;
38

39
    auto table1 = get_kmp_table(s);
40
    string ss = s;
41
    reverse(ss.begin(), ss.end());
42
    auto table2 = get_kmp_table(ss);
43

44
    return (validate_table(table1) && validate_table(table2));
45
  }
46
};