计算给定的字符串的所有可能的子串 [英] Computing All The Possible Substrings of a Given String

问题描述

可能重复：
  如何找到一个字符串的所有子在PHP
  查找列表的所有子集

Possible Duplicate:
How to find all substrings of a string in PHP
Find all subsets of a list

我怎么能计算出一个字符串的所有可能的子？例如，给定一个字符串ABCDE。其所有可能的子字符串将是

How can I compute all the possible substrings of a string? For example given a string ABCDE. All its possible substrings will be

A， B， C， 研发， E， AB， 公元前， 光盘， DE， 美国广播公司， BCD， CDE， A B C D， BCDE， ABCDE

A, B, C, D, E, AB, BC, CD, DE, ABC, BCD, CDE, ABCD, BCDE, ABCDE

谢谢！伪code就会有强烈的AP preciated。 ：D

Thanks! A pseudocode will be highly appreciated. :D

推荐答案

仅仅使用两个for循环：

Just use two for-loops:

generate substrings(string):
    for start in [0,1,...,string.length-1]:
        for end in [start,...,string.length-1]:
            yield string[start...end]

您也可以做这样的两个for循环：

You can also do it this way with two for-loops:

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 ""

您可能希望包括空字符串，的顺序返回为好，因为它是所有字符串的子串。

You probably want to include the empty string "" in the sequence you return as well, as it is a substring of all strings.

您还需要考虑它是否有效产生重复的字符串多次（比如，你回到ABA两倍亚的斯亚贝巴的子串？）。如果答案是否定的，仅仅是做一个叫做哈希表 alreadyYielded ，每当你屈服，放弃，如果你已经得到的字符串，否则万一值添加到哈希表你再看到它。例如：

You also need to consider if it is valid to yield a duplicate string multiple times (e.g. do you return "ABA" twice as a substring of "ABABA"?). If the answer is no, merely make a hashtable called alreadyYielded, and whenever you yield, abort if you've already yielded the string, otherwise add the value to the hashtable in case you see it again. For example:

seen = new HashTable()
...
        substring = string[...]
        if substring not in seen:
            seen.add(substring)
            yield substring
...

这篇关于计算给定的字符串的所有可能的子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！