语言独立性：检查一个字符串是否包含特定子字符串的倍数

Question

我希望通用算法能够查找字符串是否包含重复模式，并且没有任何部分字符串不在重复模式之外。

例如，看看这些样品字符串：

abcabcabc - true 
abcabcabcx - false 
cucumbercucumber - true 
cucumber - false 
abaaabaaabaa - true 

我看着this answer，这解决了这个问题的几个案例，但在cucumber例子的情况下会失败。我需要一些可以在所有情况下都有效的东西。

Answer 1

一个Python溶液通过https://stackoverflow.com/a/2553533/1763356启发是

s in (s + s)[1:-1] 

这需要O(n)时间假设的高效实现的str.__contains__。

Answer 2

这似乎是明显的方式做到这一点：

String s = "abaaabaabaa" ; // string to test 

for (int repeating_pattern_length=1; 
    repeating_pattern_length<=s.length/2; 
    repeating_pattern_length++) 
{ if (modulo(s.length,repeating_pattern_length)==0) 
    { // can fit exactly N times 
    String proposed_subpattern=s.substring(0,repeating_pattern_length); 
    for (nth_instance=2; // don't need to check 1st occurrence 
      nth_instance<=s.length/repeating_pattern_length; 
      nth_instance++) 
    { // check nth occurrence 
     if (!proposed_subpattern.equal(
      s.substring((nth_instance-1)*repeating_pattern_length, 
         repeating_pattern_length) 
      cycle repeating_pattern_length; // nth occurrence doesn't match 
    } 
    return true; 
    } 
} 
return false; 

[未测试。这是为了Java，但我不是专家的Java编码器。原谅我的过犯]。

这可以说具有小的常数因子的复杂度O（s.length）。

有人可能会考虑建立一个后缀树（也是线性时间），然后检查树是否有适当的周期。我怀疑上述算法在实践中是相当不错的。

Answer 3

由于您并未要求特定语言，因此我建议您查看Repeating String的Rosetta代码页。你可以找到并研究一堆解决问题的算法。 尽管在Rosetta Code中针对1和0说明了问题，但大多数解决方案都应该使用任何可能的字符串。

我写了一个普通的Common Lisp递归解决方案，这里的注释代码：

(ql:quickload :alexandria) 
(defun rep-stringv (a-str &optional (max-rotation (floor (/ (length a-str) 2)))) 
    ;; Exit condition if no repetition found. 
    (cond ((< max-rotation 1) "Not a repeating string") 
     ;; Two checks: 
     ;; 1. Truncated string must be equal to rotation by repetion size. 
     ;; 2. Remaining chars (rest-str) are identical to starting chars (beg-str) 
     ((let* ((trunc (* max-rotation (truncate (length a-str) max-rotation))) 
       (truncated-str (subseq a-str 0 trunc)) 
       (rest-str (subseq a-str trunc)) 
       (beg-str (subseq a-str 0 (rem (length a-str) max-rotation)))) 
      (and (string= beg-str rest-str) 
       (string= (alexandria:rotate (copy-seq truncated-str) max-rotation) 
         truncated-str))) 
     ;; If both checks pass, return the repeting string. 
     (subseq a-str 0 max-rotation)) 
     ;; Recurse function reducing length of rotation. 
     (t (rep-stringv a-str (1- max-rotation))))) 

测试：

CL-USER> (rep-stringv "cucumber") 
"Not a repeating string" 
CL-USER> (rep-stringv "abaaabaaabaa") 
"abaa" 

最佳的解决方案可以用suffix tree来实现的字符串，因为你现在可能已经 - 因为这是一个随处可见的常见问题，例如，Wikipedia。

实现它似乎矫枉过正，除非你真的需要性能。在任何情况下，后缀树的例子（在许多语言中）可以找到here。

Answer 4

下面是一些基本的C++代码，没有工作：

bool IsRepeating(std::string in) { 

    int totalLength = in.length(); 
    for (int subLength = 1; subLength <= totalLength/2; subLength++) { 
     if (totalLength % subLength != 0) continue; 

     for (int startPos = 0; startPos < subLength; startPos++) { 
      char startChar =in[startPos]; 
      bool mismatchFound = false; 
      for (int delta = subLength; delta < totalLength-startPos; delta += subLength) { 
       if (in[startPos+delta] != startChar) { 
        mismatchFound = true; 
        break; 
       } 
      } 
      if (mismatchFound) { 
       break; 
      } 
      return true; 
     } 
    } 
    return false; 
} 

它利用的子串长度必须总字符串长度的约数的事实。

最糟糕的时间复杂度非常糟糕，就像O（n^2 log（log（n））），但我不确定。 （最糟糕的情况是，当字符串由两个完全相同的子字符串组成时）。我仍然认为平均而言，它应该表现得相当好，因为大多数外部循环体只对字符串长度的除数执行，并且内部循环尽快中止因为发现不匹配。

编辑：@Veedrac的解决方案不仅更优雅，而且在大多数情况下也更高效。对于直接比较，这里是C++版本：

bool IsRepeating(const std::string& in) { 
    if (in.length() < 1) return false; 
    return (in + in).substr(1, 2 * in.length() - 2).find(in) != std::string::npos; 
} 

它确实使用更多的内存。如果您不知道该功能的用途，可能很难弄明白。但这也适用于我的原始版本。