计算给定字符串的所有可能的子字符串

发布于 2024-12-18 12:13:32 字数 458 浏览 2 评论 0原文

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

如何计算 a 的所有可能的子字符串细绳？例如给定一个字符串 ABCDE。它所有可能的子串都是

A，乙， C、 D、乙， AB, 公元前，光盘，德, ABC, 二进制码， CDE, ABCD, BCDE, ABCDE

谢谢！伪代码将受到高度赞赏。：D

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

初心 2024-12-25 12:13:32

只需使用两个 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
...

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]

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.

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

回复收藏 0 原文

哽咽笑 2024-12-25 12:13:32

这是一个 2 美分的答案：

for (indexOfFirstLetterOfString = 0; indexOfFirstLetterOfString < string.length; indexOfFirstLetterOfString++) {

   for (indexOfLastLetterOfString = indexOfFirstLetterOfString + 1; indexOfLastLetterOfString < string.length; indexOfLastLetterOfString++) {

        addToArrayOfStrings ( string.substring (indexOfFirstLetterOfString, indexOfLastLetterOfString - indexOfFirstLetterOfString))
        incrementCounter();

    }
}

要获得组合的数量，只需在内循环中添加一个计数器即可。

例如，在 Perl 中，这可能看起来像：

$a = "ABCDE";

$numberOfSubstrings = 0;

for ($indexOfFirstLetter = 0; $indexOfFirstLetter <= length($a); $indexOfFirstLetter++) {

    for ($indexOfLastLetter = $indexOfFirstLetter + 1; $indexOfLastLetter <= length($a); $indexOfLastLetter++)  {
        print substr($a, $indexOfFirstLetter, $indexOfLastLetter - $indexOfFirstLetter) . "\n";

        $numberOfSubStrings++;
    }
}

print "Number of substrings: " . $numberOfSubStrings;

Here's a 2-cent answer:

for (indexOfFirstLetterOfString = 0; indexOfFirstLetterOfString < string.length; indexOfFirstLetterOfString++) {

   for (indexOfLastLetterOfString = indexOfFirstLetterOfString + 1; indexOfLastLetterOfString < string.length; indexOfLastLetterOfString++) {

        addToArrayOfStrings ( string.substring (indexOfFirstLetterOfString, indexOfLastLetterOfString - indexOfFirstLetterOfString))
        incrementCounter();

    }
}

To get the number of combinations, simply add a counter to the inner loop.

For instance, in perl, this might look like:

$a = "ABCDE";

$numberOfSubstrings = 0;

for ($indexOfFirstLetter = 0; $indexOfFirstLetter <= length($a); $indexOfFirstLetter++) {

    for ($indexOfLastLetter = $indexOfFirstLetter + 1; $indexOfLastLetter <= length($a); $indexOfLastLetter++)  {
        print substr($a, $indexOfFirstLetter, $indexOfLastLetter - $indexOfFirstLetter) . "\n";

        $numberOfSubStrings++;
    }
}

print "Number of substrings: " . $numberOfSubStrings;

回复收藏 0 原文

~没有更多了~