在字符串中查找所有分割子串的出现位置

Question

我正在尝试解决一个有点特别的问题。我需要找出一个字符串中所有出现的子串的数量，而这个子串不一定要是连续的。

---

举个例子：

输入：

adnndaend

我想找到子串 and。

出现的情况：

adnndaend

adnndaend

adnndaend

adnndaend

adnndaend

adnndaend

输出：

6

---

我尝试使用 Python 的 re.findall 来获取出现的列表：

re.findall('^.*a.*n.*d.*$', 'adnndaend')

但是它返回的列表只有一个项目 - 整个字符串：

['adnndaend']

所以你能告诉我，我的正则表达式哪里出错了吗？或者给我一个更好的解决方案？最好是用 Python 或 Java，因为我对其他语言不太熟悉。

Answer 1

你可以使用 itertools.combinations，方法如下：

import itertools
pattern = "and"
print len([''.join(i) for i in itertools.combinations('adnndaend',len(pattern) if ''.join(i) == pattern])

输出结果：

6

这个想法是用 itertools.combinations 生成所有字符序列的组合，然后把这些组合和你的模式进行匹配；最终得到的列表只会包含匹配的项。

Answer 2

public int findOccurrences(String str, String key) {
    int total = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == key.charAt(0)) {
            if (key.length() > 1) {
                total += findOccurrences(str.substring(i), key.substring(1));
            } else {
                total += 1;
            }
        }
    }
    return total;
}

@Test
public void yup(){
    System.out.println(findOccurrences("adnndaend", "and"));
}

输出结果是6

Answer 3

正则表达式返回的是不重叠的匹配结果，在你的情况下只会找到一个匹配。所以用正则表达式就不合适了。相反，我想出了一个小的递归函数：

def count(haystack, needle):
    result= 0
    pos= -1
    char= needle[0] # we'll be searching the haystack for all occurences of this character.

    while True:
        # find the next occurence
        pos= haystack.find(char, pos+1)

        # if there are no more occurences, we're done
        if pos==-1:
            return result

        # once we found the first character, recursively count the occurences of
        # needle (without the first character) in what's left of haystack
        if len(needle)==1:
            result+= 1
        else:
            result+= count(haystack[pos+1:], needle[1:])

我没有进行过多的测试，但：

>>> print count('adnndaend', 'and')
6

Answer 4

你可以得到字母 a、n 和 d 出现的所有组合：

from itertools import combinations
def sub_s(st,word):
   all_s = (x for x in st if x in word)
   return len([x for x in (combinations(all_s, len(word))) if "".join(x) == word] )