使用分治法在字符串中出现模式的频率

问题 :

给定具有n个字符的字符串S和具有k个字符的模式P, 出现的一个自然问题是 P 出现在S中。例如,如果 S = CGATATATCCATAG 和 P = ATA ,则P在中出现三次 S ;也就是说, FREQ(S,P) = 3 。另一方面,当 P′ = AAT , FREQ(S,P′) = 0 因为在 S 等于 AAT 。

a.给定S和P,设计一个蛮力算法(即最基本的算法),输出 FREQ(S,P) .你的算法运行时间是多少?你的答案应该是n和k。

b.这一次,设计一个分而治之的算法,输出 频率(S,P) .你的算法运行时间是多少?你的答案应该是 n 和 k 。

解决方案 :

a) 我们使用移动窗口的方法来检查所有的可能性。

def FREQ(S,k):
  count = 0
  for i in [0...length(S) - k]:
    if S.substring(i, length(k)) == k:
      count = count + 1
  
  return count

此循环运行 length(S) - length(k) + 1 因此该算法运行的次数 O(|S| - |k| + 1) 时间。

b) 我不确定如何使用分而治之,也不确定是否有什么能战胜线性时间复杂性。