C语言 | Leetcode C语言题解之第459题重复的子字符串

题目：

题解：

bool kmp(char* query, char* pattern) {int n = strlen(query);int m = strlen(pattern);int fail[m];memset(fail, -1, sizeof(fail));for (int i = 1; i < m; ++i) {int j = fail[i - 1];while (j != -1 && pattern[j + 1] != pattern[i]) {j = fail[j];}if (pattern[j + 1] == pattern[i]) {fail[i] = j + 1;}}int match = -1;for (int i = 1; i < n - 1; ++i) {while (match != -1 && pattern[match + 1] != query[i]) {match = fail[match];}if (pattern[match + 1] == query[i]) {++match;if (match == m - 1) {return true;}}}return false;
}bool repeatedSubstringPattern(char* s) {int n = strlen(s);char k[2 * n + 1];k[0] = 0;strcat(k, s);strcat(k, s);return kmp(k, s);
}