string - 环绕字符串的唯一子字符串

Question

我得到了字符串 str="abcdefghijklmnopqrstuvwxyz" 的无限环绕，所以它看起来像"..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." 和另一个字符串 p.

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

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

我尝试在字符串 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？有没有更好的方法来解决这个问题？

Answer 1

一些想法/建议(不是完整的算法)

1. 您不需要考虑环绕字符串的无限重复，而只需考虑 len(p)/len(repeating-fragment) + 1(整数除法)重复。让我们用 S **
表示这个字符串
2. 如果 p 的子串 sp 是 S 的子串，则 sp 的任何子串都将是S
的子字符串

所以问题似乎减少到:

• 找到最大长度的sp(p 和S 的子串)。这叫做 longest common substring并承认复杂度为 O(n*m)(两个字符串的长度)的动态规划解决方案。引用有一个伪代码算法。
• 在消除最长公共(public)子串后，用 p 的“剩余部分”递归地重复上述操作。

现在，您有了一系列“最长公共(public)子串”。你需要保留多少？我觉得“最长公共(public)子串”可以用来减少暴力破解上述所有子串的需要，但我需要比现在更多的时间。

希望上面的草图对您有所帮助。

---

** 我在需要考虑的重复次数上可能是错误的。如果我是，那么在任何情况下都将考虑最大重复次数，并且将有一个满足该目的的最小长度的 S。