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);
}
原文地址:https://blog.csdn.net/m0_59237910/article/details/142722126
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!