独特的子串绕串包装

我一直在考虑串绕的无限包装海峡=“ABCDEFGHIJKLMNOPQRSTUVWXYZ”所以它看起来像 “..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd ......”和另一个字符串p。独特的子串绕串包装

我需要找出p无限环绕字符串str中存在多少个唯一的非空子字符串p？

For example: "zab" 
There are 6 substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in str.

我试图找到p的所有后缀在字符串的特定串联海峡例如说：“abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz”

，一旦我得到一个后缀这是一个以上部分我将其所有子串添加到我的结果中，如下所示：

  for (int i=0;i<length;i++) { 
      String suffix = p.substring(i,length); 
      if(isPresent(suffix)) { 
       sum += (suffix.length()*(suffix.length()+1))/2; 
       break; 
      } else { 
       sum++; 
      } 
     }

而且我isPresent功能是：

 private boolean isPresent(String s) { 
      if(s.length()==1) { 
       return true; 
      } 
      String main = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcde 
fghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"; 
      return main.contains(s); 

     }

如果P的长度比isPresent功能假设我假定连接字符串时，我的算法失败！

那么我应该如何找到子字符串，而不管环绕字符串str？这个问题有更好的方法吗？

来源

2016-12-04 poorvankBhatia

一些想法/建议（不是一个完整的算法中）

你不需要考虑字符串周围包裹的无限重复，但只有len(p)/len(repeating-fragment) + 1（整数分频）重复。让我们来表示该字符串S**
如果子的psp是S一子，比sp任何子将是S

子所以，问题似乎减少到：

找到sp（p和S的子串）与最大长度。这被称为longest common substring并承认动态编程解决方案的复杂性为O(n*m)（两个字符串的长度）。引用了一个伪代码算法。
在消除最长的公共子串后，用p的“残余”递归地重复上述过程。

现在，你有一个“最长的常见子串”序列。你需要保留多少？我觉得“最长的公共子串”可以用来减少强制任何以上所有子串的需求，但是我需要比现在更多的时间。

我希望上面的草图有帮助。

**我可能是错上需要考虑重复的次数。如果我是，那么在任何情况下都会有一个最大的重复次数要考虑会有最小长度的S足以为宗旨。

来源

2016-12-04 05:24:58

独特的子串绕串包装

回答

相关问题