Удаление всех вхождений шаблона p из строки s в O (s + p) time

Question

Как удалить все вхождения шаблона p из строки в O(s+p) времени?

как если

String S = AAAAAAAAB 

pattern P = AAAAAA 

то результирующая строка должна быть Аргументы B

только

Answer 1

Сначала вам нужно найти все из них в O(S+P). Соответствующий алгоритм Кнута-Морриса-Пратта делает это. Псевдокод от its wikipedia page:

algorithm kmp_search: 
    input: 
     an array of characters, S (the text to be searched) 
     an array of characters, W (the word sought) 
    output: 
     an integer (the zero-based position in S at which W is found) 

    define variables: 
     an integer, m ← 0 (the beginning of the current match in S) 
     an integer, i ← 0 (the position of the current character in W) 
     an array of integers, T (the table, computed elsewhere) 

    while m + i < length(S) do 
     if W[i] = S[m + i] then 
      if i = length(W) - 1 then 
       Found one Match here: 
       It is from S[m] to S[m+i] 
       You just need to delete it. 
      let i ← i + 1 
     else 
      if T[i] > -1 then 
       let m ← m + i - T[i], i ← T[i] 
      else 
       let i ← 0, m ← m + 1 

    (if we reach here, we have searched all of S unsuccessfully) 
    return the length of S