当前位置：首页 > article >正文

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

article 2024/10/7 23:17:58

题目：

题解：

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);
}

查看全文

http://www.kler.cn/news/336614.html