计数在一些查询字符串中的字符出现的次数？

我想找到一个人物的出现在N次查询字符串：例如字符串是：“i_love_mathematics” 和任务是找出发生：计数在一些查询字符串中的字符出现的次数？

“我”的范围：

  1-4(a substring starting from 1st character and ending at 4th) 
      2-5 
      3-10

在范围

'_'：

  1-10 
      3-9

输出将是：

类似的问题是要找到字符串中的字符出现的次数，但对于复杂度为O（N），但在这种情况下，如果我这样做，这将导致非常高的复杂性，有没有可以用来解决这个问题的数据结构？

2017-03-03 ash

复杂性将是'O（q * n）'，其中'q'是查询的数量，'n'是字符串的长度，如果你想要一个简单的实现。或者，你可以用一棵树来降低复杂度为'O（q log n）'，空间复杂度为'O（n）'。或者，您可以使用一张表格将每个字符映射到特定字符出现的索引列表。复杂性将保持不变。 – Paul

我们将保持每个字符的出现次数在每个位置，例如串abacaba

a b a c a b a 
| |1|2|3|4|5|6|7 
a | 1 1 2 2 3 3 4 
b | 0 1 1 1 1 2 2 
c | 0 0 0 1 1 1 1

现在，如果我们想回答一个查询我们下面

字母“a '在范围3-5中

我们在位置5减去位置3之前的出现次数，即[5] -a [3-1] = 3-1 = 2，出现了2次出现的字母'A' 在范围3至5

2017-03-03 14:49:08 EmmanuelAC

用于搜索每一个查询将‰范围时间复杂度（N * Q）

N：字符串长度

问：节数查询

但是有一个更好的办法要做到这一点您可以使用segment trees。

时间为树构造复杂度为O（N），并为每个查询是O（日志（n））的

因此，对于Q查询时间复杂度是O（Q *的log（n））

2017-03-03 16:23:48

回答