string - 在 O(s+p) 时间内从字符串 s 中删除所有出现的模式 p

Question

如何及时从字符串中删除模式 p 的所有出现O(s+p)？

就像如果

String S = AAAAAAAAB

pattern P = AAAAAA

那么结果字符串应该只有 B

Answer 1

First you need to find all of them in O(S+P). Knuth-Morris-Pratt Substring Matching algorithm does it. Pseudocode from 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