检查字符串是否是未知子字符串的重复 [英] Check if string is repetition of an unknown substring

问题描述

我正在尝试编写一个正则表达式或 Ruby 方法，它会在字符串中找到最长的重复模式.例如:

I'm trying to write a regex or Ruby method which will find the longest repeated pattern in a string. For example:

"abcabc"  => "abc"  
"cccc" => "c"
"abcd" => "abcd"

实现此目的的最佳方法是什么?我天真地尝试了 /^(.*)*$/ 但这不起作用，因为它只匹配完整的字符串.

What is the best way to implement this? I naïvely tried /^(.*)*$/ but that won't work as it just matches the full string.

推荐答案

我知道事情不会那么复杂，所以我想了想，找到了一个解决方案:

I knew it couldn't be that complicated, so I thought it over and found a solution:

def unrepeat(str)
  n = str.size

  newstr = str
  n.times do |i|
     newstr = newstr[-1] + newstr[0..-2]
     if newstr == str
        return i + 1
     end
  end
end

这将返回重复模式的长度.它通过生成字符串的旋转来找到它.

This will return the length of the repeated pattern. It finds this by generating rotations of the string.

这篇关于检查字符串是否是未知子字符串的重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！