leetcode459：重复的子字符串（repeated-substring-pattern）

[carloscn]

问题描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1: 输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。

示例 2: 输入: s = "aba" 输出: false

示例 3: 输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示： 1 <= s.length <= 104 s 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/repeated-substring-pattern

[carloscn]

问题分析

我们可以这样，掐头和去尾的字符串拼接在一起，然后判断输入是否为子串，如果是的话就证明是重复的子串。

static int32_t repeat_sub_pattern(char *input_str, bool *result)
{
    int32_t ret = 0;
    size_t str_len = 0;
    char *sub = NULL;

    UTILS_CHECK_PTR(input_str);
    UTILS_CHECK_PTR(result);
    UTILS_CHECK_LEN(str_len = strlen(input_str));

    sub = (char*) malloc(2 * str_len - 1);
    UTILS_CHECK_PTR(sub);

    memset(sub, '\0', 2 * str_len - 1);
    strncat(sub, input_str + 1, str_len - 1);
    LOG("the sub is %s\n", sub);
    strncat(sub, input_str, str_len - 1);
    LOG("the sub is %s\n", sub);

    *result = strstr(sub, input_str);
    LOG("the compare sub is %s and input %s\n", sub, input_str);

finish:
    if (sub != NULL) {
        free(sub);
    }
    return ret;
}

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/str/29_repeated-substring-pattern_459.c

result: