<p>我对Python并不精通,但可以很容易地描述您需要的算法:</p>
<pre><code>found <- false
length <- inputString.length
size = 1
output <- inputString
while (not found) and (size <= length / 2) do
if (length % size = 0) then
chunk <- inputString.substring(0, size)
found <- true
for (j <- 1,length/size) do
if (not inputString.substring(j * size, size).equals(chunk)) then
found <- false
if end
for end
if found then
output <- chunk
if end
if end
size <- size + 1
while end
</code></pre>
<p>这个想法是越来越多地从字符串的开头开始取子字符串,子字符串的起始长度是1,当你没有找到一个重复的循环时,你增加长度(直到它显然不再可行,也就是说,已经达到输入长度的一半)。在每次迭代中,比较子字符串的长度和输入字符串的长度,如果输入字符串的长度不能与当前子字符串整除,那么当前的子字符串对于输入字符串将不会重复(一种优化方法是找出输入字符串的长度可整除的数字,并只检查子字符串中的长度,但是为了便于理解,我避免了这种优化)。如果字符串的大小可以被当前大小整除,那么可以从输入字符串的开头一直取子字符串直到当前大小,并检查是否重复。第一次找到这样的模式时,可以停止循环,因为您已经找到了解决方案。如果找不到这样的解决方案,则输入字符串是最小的重复子字符串,并且重复0次,因为它只在字符串中找到一次。你知道吗</p>
<p>编辑</p>
<p>如果希望允许最后一次出现仅是模式的一部分,并受inputString的限制,则可以如下更改算法:</p>
<pre><code>found <- false
length <- inputString.length
size = 1
output <- inputString
while (not found) and (size <= length / 2) do
chunk <- inputString.substring(0, size)
found <- true
for (j <- 1,length/size) do
if (not inputString.substring(j * size, size).equals(chunk)) then
found <- (chunk.indexOf(inputString.substring(j).length) = 0)
if end
for end
if found then
output <- chunk
if end
size <- size + 1
while end
</code></pre>
<p>在这种情况下,我们看到</p>
<pre><code> found <- (chunk.indexOf(inputString.substring(j).length) = 0)
</code></pre>
<p>因此,在不匹配的情况下,我们检查块是否以字符串的剩余部分开始。如果是这样,那么我们就在输入字符串的末尾,并且模式部分匹配到字符串的末尾,所以found将为true。如果没有,那么发现将是假的。你知道吗</p>