Leetcode-459 Repeated Substring Pattern

459 Repeated Substring Pattern

判断字符串是否为子串重复构成，输入字符串的长度在10000内。

例如，’abab’由’ab’循环两次构成，’aa’由’a’循环两次构成。

1. 解决思路

1.1 双指针

双指针是最直接的方式，固定头指针的位置，移动尾指针，知道找到一个重复的子串，然后对剩余的部分进行子串验证。

如果字符串是由子串重复生成的，则一定存在一个最小子串。例如，’aaaa’由’aa’重复两次构成，同时也是’a’重复四次构成。但’aa’是’a’重复两次构成的，因此，识别出最小子串’a’即可。

双指针法的时间复杂度为O(n²)，空间复杂度为O(1)。

bool repeatedSubstringPattern(char *s){
    if (s == NULL) {
        return false;
    }
    bool result = false;

    char *begin = s;
    char *end = s + 1;
    while (*end != 0) {
        while (*end != 0 && *begin != *end) {
            ++ end;
        }
        if (*end == 0) {
            break;
        }

        char *temp_end = end;
        char *temp_begin = begin;
        while (*temp_end != 0 && *temp_begin == *temp_end) {
            ++ temp_begin;
            ++ temp_end;
        }
        if (*temp_end == 0 && (temp_end - end) % (end - begin) == 0) {
            result = true;
            break;
        }

        ++ end;
    }

    return result;
}

1.2 掐头去尾

假设一个字符串有子串重复构成，则第一个字符一定是子串的首字符，同时最后一个字符为子串的尾字符。

所谓掐头去尾，分别包括掐头和去尾两步。如果字符串由子串重复构成，则字符串中的子串至少出现一次，掐头则破坏了第一个子串，去尾则破坏了最后一个子串。将掐头及去尾的结果拼接，如果中间的部分与原字符串一致，则意味着符合重复条件。

例如，’abcabcabc’由’abc’重复三次构成，掐头后剩余’bcabcabc’，去尾后剩余’abcabcab’，拼接得到’bcabcabcabcabcab’，重复的结果只剩下四次。在’bcabcabcabcabcab’中搜索’abcabcabc’，如果匹配，则证明符合重复规则。

如果S由一系列子串构成，即S₁ S₂ S₃ … S_i … S_n。如果S由子串重复构成，则S₁ = S₂ = S₃ = S_i = S_n。掐头即破坏S₁，去尾即破坏S_n，拼接后的构成为S₂ S₃ … S_i … S_n S₁ S₂ S₃ … S_i … S_n-1。当拼接结果中仍然存在S，则满足S₂ = S₁，S₃ = S₂，S_{i + 1} = S_i，S_n = S_{n - 1}，S_n = S₁，汇总即S₁ = S₂ = S₃ = S_i = S_n。

掐头去尾的时间复杂度为O(n)，空间复杂度为O(n)。

bool repeatedSubstringPattern(char *s){
    if (s == NULL) {
        return false;
    }
    bool result = false;

    int s_len = strlen(s);
    char *s_s = (char *)malloc(sizeof(char) * s_len * 2 - 2);

    memcpy_s(s_s, s_len * 2 - 2, s + 1, s_len - 1);
    memcpy_s(s_s + s_len - 1, s_len - 1, s, s_len - 1);

    for (int index = 0 ; index <= s_len - 2 ; ++ index) {
        if (*s == *(s_s + index) && memcmp(s, s_s + index, s_len) == 0) {
            result = true;
            break;
        }
    }

    free(s_s);
    return result;
}