string - 计算多个查询中字符串中某个字符的出现次数？

Question

我想在 n 个查询的字符串中找到一个字符的出现：例如，字符串是：“i_love_mathematics”，任务是找到：

“我”在范围内：

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

'_' 在范围内：

           1-10
           3-9

输出将是：

           1
           0
           0
           2
           1

类似的问题是查找字符串中字符的出现次数，但复杂度为 O(N) 但在这种情况下，如果我这样做会导致非常高的复杂度，是否有一种数据结构可以可以用来解决这个问题吗？

Answer 1

我们将保留每个字符在每个位置的出现次数，例如字符串 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

现在，如果我们想回答一个查询，我们执行以下操作

3-5 范围内的字母“a”

We do a at position 5 minus number of occurrences before position 3, that is a[5]-a[3-1]=3-1=2 there are 2 occurrences of the letter 'a' in range 3 to 5

Answer 2

Time complexity for searching the range for each and every query would be O(n*q)

n: length of string

q: no.of queries

But there is a better way to do it You can use segment trees.

Time complexity for tree construction is O(N) and for each query is O(log(n))

So, for q queries Time complexity would be O(q*log(n))