首页 文章

计算给定字符串的所有可能的子字符串[重复]

提问于
浏览
4

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

如何计算字符串的所有可能子串?例如给出一个字符串ABCDE . 所有可能的子串都将是

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

谢谢!伪代码将受到高度赞赏 . :d

2 回答

  • 2

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

    这是一个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;
    

相关问题