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

Question

我想为 n 个查询查找字符串中某个字符的出现次数: 例如字符串是:“i_love_mathematics” 任务是找到:

'i' 在范围内:

          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”

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