LeetCode-459. Repeated Substrin

Description
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:
Input: "aba"
Output: False

Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

题目分析

本题要求判断一个字符串是否可以由它的某个前缀通过复制得到，例如字符串"abcabcabcabc"可以由前缀"abc"复制3次得到，或者由前缀"abcabc"复制两次得到，因此返回true。而字符串"aba",不能通过复制"a"或者"ab"得到，故返回false。
注意：题目要求是前缀而不是字符串的某些字符组成的子集，例如"aabb",不能认为可以通过复制"ab"得到，而是字符串"aabb"不能通过复制"a"或者"aa"得到，因此应该返回false。

解题思路

如果一个字符串可以通过复制其某个前缀得到，因此该前缀的首个字符，必定是字符串的首个字符，而字符串的最后一个字符(注意不是'\0')，必定是该前缀的最后一个字符。因此如果将输入字符串str1（假设长度为L）复制两次，生成str2，然后将str2的首个字符和最后一个字符(注意不是'\0')去掉生成str3。如果str3中的某L个连续字符子集正好是字符串str1，则说明字符串str1可以通过复制某个前缀得到，因此返回true，否则返回false。
例如：

str1="abab";
str3="bababa";

str3中从第2个元素到第5元素的4个字符子集正好是str1，因此返回true。

在比较str3中的某L个连续子集是否就是str1时，需要逐个比较，第一次从str3的首个字符开始，连续比较L个，第二次，从str3的第二个字符开始，连续比较L个，依次比较L次。若在以某个字符开始的L个与str1比较中，相对应的字符不一致，则结束以该字符为首个字符的比较，开始进行以下一个字符为首的比较；如果L个连续字符与str1完全一致，则返回true。程序初始设置结果为false。

C语言代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

bool repeatedSubstringPattern(char* s) {
    int i=0,j=0;
    bool flag=false;
    int size1=strlen(s);
    char string[size1*2];
    strcpy(string,s);
    strcat(string,s);                    //复制字符串
    size2=strlen(s);
    for(i=1;i<size1;i++)                 //去掉首、尾，因此string第2个字符(首个字符去掉)开始
    {   
        for(j=0;j<size1;j++)
        {
            if(string[i+j]!=s[j])        //若发现相对应的字符不一致，则接受本级循环比较
                {
                    break;
                }
        }
        if(j==size1)                     //相对应的字符完成一致
        {
            flag=true;
            break;
        }
    }
     return flag;
}


int main()
{
    char* strs="aaaa" ;
    bool flag;
    
    flag=repeatedSubstringPattern(strs);
    printf("flag=%d",flag);
    return 0;
}

参考文献
[1] https://leetcode.com/problems/repeated-substring-pattern/#/description
[2] https://discuss.leetcode.com/topic/71510/my-9-ms-c-solution-with-complexity-of-o-n-with-clear-explanation
[3] http://wowx.info/posts/posts/2016122223541811/