String Find/Replace Algorithm

Question

Я хотел был бы иметь возможность искать строку для различных слов, когда я нахожу ее, я хочу разбить строку в этой точке на 3 части (слева, матч, справа), согласованный текст будет исключен, и процесс будет продолжен с новой строкой left + right.

Теперь, когда у меня есть все мои матчи, мне нужно отменить процесс, вставив соответствующие слова (или их замену) в том месте, где они были удалены. Я никогда не находил того, чего хотел в любом из моих поисков, поэтому я подумал, что попрошу ввести здесь здесь.

Пожалуйста, дайте мне знать, если этот вопрос нуждается в дальнейшем описании.

Это цель:

one two three four five six 

матч «три» заменить обув (помните, мы нашли три, и где мы его нашли)

one two four five six 
     | 
    three 

матч «два четыре» и предотвратить его от подгонки чего-либо (отредактировано для ясности)

на данный момент, вы не можете сравниться, например, "on е два»

все матчи были найдены, теперь поместить их замены назад в (в обратном порядке)

one two four five six 
     | 
    three 


one two foo four five six 

Какой смысл? Предотвращение сопоставления текста замены одного образца другим шаблоном. (все шаблоны запускаются одновременно и в том же порядке для каждой обрабатываемой строки)

Я не уверен, что язык имеет значение, но я использую Lua в этом случае.

Я попробую перефразировать, у меня есть список шаблонов, которые я хочу найти в заданной строке, если я найду его, я хочу удалить эту часть строки, чтобы она не соответствовала чему-либо еще, но я хочу отслеживать, где я нашел его, так что я могу вставить текст замены там однажды я сделан пытаюсь соответствовать моему списку моделей

Вот связанный с этим вопрос:

Shell script - search and replace text in multiple files using a list of strings

Answer 1

Ваше описание алгоритма неясное. Нет точного правила, когда извлеченные жетоны должны быть повторно вставлены.

Вот пример:

1. Найти «три» в «один два три четыре пять шесть»

2. Выберите один из этих двух, чтобы получить «Foo бар», как результат:

   в , заменить «один два» на «foo» и «four five six» на «bar»

   b. заменить «один два четыре пять шесть» с «Foo баром»

3. Insert «три» назад в шаг 2 результирующей строки «Foo баре»

На шаге 3 делает «три» идет перед ' бар "или после него?

После того как вы разработали четкие правила для повторного ввода, вы можете легко реализовать алгоритм как рекурсивный метод или как итеративный метод со стеком замены.

Answer 2

Учитывая структуру из проблема, я бы, вероятно, попробовал алгоритм, основанный на двоичном дереве.

Answer 3

псевдокод:

for(String snippet in snippets) 
{ 
    int location = indexOf(snippet,inputData); 
    if(location != -1) 
    { 
     // store replacement text for a found snippet on a stack along with the 
     // location where it was found 
     lengthChange = getReplacementFor(snippet).length - snippet.length; 
     for each replacement in foundStack 
     { 
      // IF the location part of the pair is greater than the location just found 
      //Increment the location part of the pair by the lengthChange to account 
      // for the fact that when you replace a string with a new one the location 
      // of all subsequent strings will be shifted 
     } 

     //remove snippet 
     inputData.replace(snippet, ""); 
    } 
} 

for(pair in foundStack) 
{ 
    inputData.insert(pair.text, pair.location); 
} 

Это в основном просто делает именно так, как вы сказали, в вашем описании проблемы. Шаг через алгоритм, помещая все в стек с местоположением, в котором он был найден. Вы используете стек, поэтому, когда вы повторно вставляете во вторую половину, это происходит в обратном порядке, так что сохраненное «местоположение» относится к текущему состоянию inputString.

Отредактировано потенциальным исправлением для критики комментатора.Прокомментировал ли блок в первой учетной записи критику или все еще не работает в определенных сценариях?

Answer 4

Что вы хотите сделать, это иметь 2-ю строку, которая хранит вывод . Вы обрабатываете вход и ищите узоры в нем. Если не найдено ни одного подходящего шаблона , замена не происходит, поэтому вы просто добавляете символы, которые вы читаете, непосредственно на вывод . Если найден шаблон , добавьте замену строку на номер . Поскольку вы всегда двигаетесь вперед в строке, нет никаких шансов на соответствие шаблону предыдущей замене.

Если вы ищете символ по символу (поиск по грубой силе), вам нужно выяснить, как вы хотите определить приоритеты шаблонов; по длине или по порядку они были добавлены в список шаблонов.

В противном случае вы будете искать слово за словом или предложением по предложению, которое обобщается на поиск с использованием буфера. Для этого вам нужно будет определить разделители (для слов это пробелы, для предложений это будут восклицательные точки периодов и другие подобные вещи, для файла значений с разделителями-запятыми это будут запятые).