查找给定字符串的显性循环子串
循环子串：
-
null
-
null
-
null
-
null
示例2：
PrefixGarbageCyclePadingGarbageCycleSufixGarbag- 返回
G:=>cycle的出现不相邻重复，G相邻重复两次
示例3：
-
null
-
null
ABCDefGHIJKLMNOPQRSTUVQXYZ- 返回
实现该算法的最佳方法是什么？
共有1个答案
找不到比这个二次时间算法更好的算法（用Python实现）：
IREP, IPER, IPOS = 0, 1, 2
def find_dominant(src):
best = (0, 0, 0) # repetitions-1, period, position
period = 0
while period < len(src) // max(2, 1 + best[IREP]):
period += 1
length = 0
for pos in range(len(src) - 1 - period, -1, -1):
if src[pos] == src[pos + period]:
length += 1
repetitions = length // period
if repetitions >= best[IREP]:
best = (repetitions, period, pos)
else:
length = 0
return best
s = "prefixgarbagecyclecyclecyclecyclesufixgarbage"
res = find_dominant(s)
if res[0] == 0:
print("nothing found")
else:
print(res[IREP] + 1, '*', s[res[IPOS]: res[IPOS] + res[IPER]])
对于每个可能的周期，扫描字符串并记住最长的周期子序列。向后扫描以检查较少的条件。在没有进一步改善的情况下停止增加。
时间复杂度为O(n2/R)，其中R为优势子串的重复次数。空间复杂度为O(1)。
-
我遇到了一个问题语句，要在给定的两个子字符串之间找到所有公共子字符串这样一种方式，在每种情况下都必须打印最长的子字符串。问题声明如下： 编写一个程序来查找两个给定字符串之间的公共子字符串。但不包括包含在较长公共子字符串中的子字符串。 null 在这种情况下，您不必使用字符串实用程序方法，如:contains、indexOf、StringTokenizer、split和replace。 我的算法是这
-
问题 你需要搜索一个字符串，并返回匹配的起始位置或匹配值本身。 解决方案 有几种使用正则表达式的方法来实现这个功能。其中一些方法被称为 RegExp 模式或对象还有一些方法被称为 String 对象。 RegExp 对象 第一种方式是在 RegExp 模式或对象中调用 test 方法。test 方法返回一个布尔值： match = /sample/.test("Sample text") # =>
-
问题 你想在一条消息中查找某个关键字第一次或最后一次出现的位置。 解决方案 分别使用 JavaScript 的 indexOf() 和 lastIndexOf() 方法查找字符串第一次和最后一次出现的位置。语法: string.indexOf searchstring, start message = "This is a test string. This has a repeat or two
-
问题内容： 我在Ubuntu上，我想在当前目录和子目录中找到名称包含字符串“ John”的所有文件。我知道可以匹配文件中的内容，但是我不知道如何在文件名中使用它。任何帮助，将不胜感激。 问题答案： 使用find命令，
-
我需要检查字符串（单词，没有空格）是否有给定字母表的任何字母。 我想有效地比较字符串和字母表。我想检查字符串是否由字母表中的字母组成。现在我的字母表在ArrayList中，在For循环中，我检查字符串是否包含ArrayList的字母，如果为true，则退出，否则继续下一个字母。上面字符串A的示例将返回false，因为p和l不是字母表的一部分。但对于B，它将返回真值。 这样做能更有效吗？谢谢你的帮助
-
我知道如何使用动态规划来解决 <罢工> 大多数 给定两个字符串的最长公共子串或最长公共子串。然而，对于字符串Y的子串X的最长子序列问题，我很难找到一个解决方案。 查找字符串X的所有子序列并按长度desc排序； 遍历排序的子序列，如果当前子序列是Y的子字符串，则返回子序列。 它可以工作，但运行时间可能会很糟糕。假设X中的所有字符都是唯一的，那么有2^m个子群，其中m是X的长度，我认为检查一个字符串是