<分区>
Possible Duplicate:
How to find all substrings of a string in PHP
Find all subsets of a list
如何计算字符串的所有可能子串?例如给定一个字符串 ABCDE。它所有可能的子串都是
一个, 乙, C, , 乙, AB, 公元前, 光盘, 德, 美国广播公司, BCD, 开发环境, A B C D, BCDE, ABCDE
谢谢!伪代码将受到高度赞赏。 :D
<分区>
Possible Duplicate:
How to find all substrings of a string in PHP
Find all subsets of a list
如何计算字符串的所有可能子串?例如给定一个字符串 ABCDE。它所有可能的子串都是
一个, 乙, C, , 乙, AB, 公元前, 光盘, 德, 美国广播公司, BCD, 开发环境, A B C D, BCDE, ABCDE
谢谢!伪代码将受到高度赞赏。 :D
最佳答案
只需使用两个 for 循环:
generate substrings(string):
for start in [0,1,...,string.length-1]:
for end in [start,...,string.length-1]:
yield string[start...end]
您也可以使用两个 for 循环以这种方式执行此操作:
generate substrings(string):
for substringLength in [1,2,...,string.length]:
for start in range [0,1,...,string.length-substringLength]:
yield string[start...(start+substringLength-1)]
yield ""
您可能还想在返回的序列中包含空字符串 ""
,因为它是所有字符串的子字符串。
您还需要考虑多次生成重复字符串是否有效(例如,您是否将“ABA”作为“ABABA”的子字符串返回两次?)。如果答案是否定的,只需创建一个名为 alreadyYielded
的哈希表,并且每当您屈服时,如果您已经产生了字符串,则中止,否则将值添加到哈希表中以防您再次看到它。例如:
seen = new HashTable()
...
substring = string[...]
if substring not in seen:
seen.add(substring)
yield substring
...
关于string - 计算给定字符串的所有可能子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8305352/