计算长度为N的二进制字符串，它们是子字符串的重复拼接

1. 介绍

在计算机科学领域中，二进制字符串是一种由0和1组成的数字序列。在本文中，我们将讨论长度为N的二进制字符串，它们由若干个子字符串重复拼接而成。

2. 算法分析

2.1 定义子字符串

定义一个子字符串是一个字符串的一部分，具有长度大于等于1的连续字符序列。例如，字符串“10101”有4个子字符串："1"、"0"、"1"、"01"、"10"、"101"、"010"、"1010" 和 "0101"。

2.2 定义重复拼接

假设有一个长度为N的二进制字符串S和它的一个长度为p的子字符串T。如果S由若干个T重复拼接而成，即S=TT...T，将S称为由T生成的字符串。例如，二进制字符串“1010”由子字符串“10”生成。

2.3 算法实现

思路：从N/2开始遍历，判断长度为i的子串是否满足重复拼接后能得到整个字符串S。

bool check(string S, int len)
{
    for(int i = 0; i < len; i++)
    {
        string T = S.substr(i, len - i);
        for(int j = 2 * len - i; j <= S.size(); j += len)
        {
            if(S.substr(j - len, len) != T)
                break;
            if(j == S.size())
                return true;
        }
    }
    return false;
}
int main()
{
    string S;
    int N;
    cin >> N >> S;
    for(int i = N / 2; i >= 1; i--)
    {
        if(check(S, i))
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

3. 算法解释

3.1 判断子串能否被重复拼接

我们可以通过遍历整个字符串S，并判断长度为i的子串是否能被重复拼接成字符串S，来判断是否存在由这个子串生成的字符串。如果存在，返回true。

bool check(string S, int len)
{
    for(int i = 0; i < len; i++)
    {
        string T = S.substr(i, len - i);
        for(int j = 2 * len - i; j <= S.size(); j += len)
        {
            if(S.substr(j - len, len) != T)
                break;
            if(j == S.size())
                return true;
        }
    }
    return false;
}

这个函数的实现很简单：它首先从S的第i个位置开始提取长度为len的子字符串T。

然后，从位置2 \* len - i开始，遍历整个字符串S。每次取长度为len的子串与T做比较，直到出现两个不同的子串或者越界。

如果所有的子串都相同，那么S可以被长度为i的子串T所重复拼接，函数将返回true。

3.2 遍历所有可能的子串长度

我们可以从长度为N/2的子串开始遍历所有可能的子串长度，知道长度为1的子串为止。当找到一个能够生成字符串S的子串T时，我们可以直接输出T的长度并退出程序。

int main()
{
    string S;
    int N;
    cin >> N >> S;
    for(int i = N / 2; i >= 1; i--)
    {
        if(check(S, i))
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

4. 总结

在本文中，我们介绍了一种用于计算长度为N的二进制字符串的算法。该算法能够确定是否存在一个子串，由它重复拼接而成的字符串等于S。我们首先定义了子串和重复拼接的概念，然后给出了算法的详细实现。具体来讲，我们通过遍历所有可能的子串长度并检查该子串是否能重复拼接成S，来确定存在的子串的长度。最后，我们给出了完整的代码实现，并讨论了算法的时间复杂度和空间复杂度。