Удаление шаблона из строки

Question

Я не уверен, как это сделать. Итак, у меня есть строка под названием S и строка шаблона M. Мне нужно удалить все вхождения M в S. Но когда я удаляю одно вхождение M в S, я мог бы создать другое. Например, учитывая слово «aajjk» и образец «aj». После первого удаления это станет «ajk». В этой новой строке появилось другое появление «aj» после первого удаления. Конечная строка после всех удалений будет тогда «k». Не могли бы вы дать мне несколько советов о том, как подойти к этой проблеме, некоторые psuedocode будут полезны, поскольку мне нужна практика в реализации.

Answer 1

В JS вы могли бы сделать что-то вроде этого:

function delPattern(patt, str) { 
    var res = str.replace(patt, ""); 
    if(patt.test(res) == true) { 
     delPattern(patt, res); 
    } else { 
     console.log(res); 
    } 

} 

var str = "aajjk"; 
delPattern(/aj/g, str); 

"PATT" это шаблон. Здесь «/aj/g». «g» означает глобальность, что каждый шаблон сопоставляется. С помощью функции «замените« вы замените свой узор на «». После этого вы спрашиваете, существует ли шаблон еще один раз «i f (patt.test (res) == true)». Если это так, повторите то же самое. Иначе дайте мне результат.

Answer 2

Упрощенный цикл, если выполнение замены приводит к другой строке. Псевдокод:

lastS = null 
while(lastS != S) 
    lastS = S 
    S.replace(M, '') 

Answer 3

Если вы хотите алгоритм линейного времени наихудший, то один подход заключается в построении конечного автомата, который принимает строки, оканчивающиеся на М (например, Кнут - Морриса - Пратта), а затем запустите этот псевдокод.

initialize a state stack to [initial state of the automaton] 
initialize an empty character stack 
for each character c in S: 
    let q be the top of the state stack 
    push delta(q, c) onto the state stack, 
     where delta is the transition function of the automaton 
    push c onto the character stack 
    if the top of the state stack is an accepting state: 
     pop length(M) values from both stacks 
output the contents of the character stack