找到字符串中每个不同字符的所有位置的最快方法

Question

Suppose we have a string, say, "122113" and we are supposed to find all the occurrences of every character in the String.

天真的方法是这样的：

string = str( raw_input() )  # for example: "122113"
distinct_char = list( set(string) )
occurrences=[]
for element in distinct_char:
    temp=[]
    for j in range(len(string)):
        if(string[j]==element):
            temp.append(j)
    occurrences.append(temp)
print(occurrences)  # output for "122113" would be [[0, 3, 4], [1, 2], [5]]
                    #because 1 occurrs at : 0, 3, 4
                    #        2 occurrs at : 1, 2
                    #        3 occurrs at : 5

But, this is quite slow if the length of the String is Large. So, is there any faster solution?

（假设字符串仅由较低的英文字母组成，字符串的长度可能为$10^12$

Answer 1

您应该使用defaultdict（默认值为空列表）并在遍历字符串时更新索引列表：

from collections import defaultdict
string = str(raw_input())
occurences = defaultdict(list)
for i, c in enumerate(string):
  occurences[c].append(i)
print occurences

然后使用列表理解获得事件列表：

occurences = [l for l in occurences.values()]

Answer 2

（对不起，我先前的回答误解了这个问题。）

你可以用^{}来表示：

import collections

very_long_string = "abcdefghij" * 1000000

indices = collections.defaultdict(list)
for i, c in enumerate(very_long_string):
    indices[c].append(i)

indices将是一个dict，它将每个字符映射到它们的索引中（显然不是上面的very_long_string的例子，而是一个较短的例子）。你知道吗

{
    "a": [0, 10],
    "b": [1, 11],
    "c": [2, 12],
    "d": [3, 13],
    "e": [4, 14],
    "f": [5, 15],
    "g": [6, 16],
    "h": [7, 17],
    "i": [8, 18],
    "j": [9, 19],
}

在我的机器上用10000个字符大约需要3秒钟。你知道吗

Answer 3

一种可能的解决方案是将字符串转换为数字，并使用数字来增加数组中的值。代码可以如下：

import numpy as np

def alph_to_num(alph):
    return ord(alph.lower())-97

string='alsblnasdglasdaoerngeaglbneronbiwernblnerl'
array=np.zeros(26)

for alph in string:
    index=alph_to_num(alph)
    array[index]=array[index]+1
print(array)

它给出：[5. 4. 0. 2. 5. 0. 3. 0. 1. 0. 0. 6. 0. 6. 2. 0. 0. 4. 3. 0. 0. 0. 1. 0. 0. 0.]

这里我已经做了长度为26的数组，因为你知道它只是小写英文字母。这也意味着更容易解释结果列表。你知道吗