Алгоритм поиска / замены строки

Question

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

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

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

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

Это цель:

one two three four five six 

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

one two four five six
       |
     three

сопоставить "два четыре" и не допустить совпадения с ним (отредактировано для ясности)

one five six
   |
 two four 
       |
     three

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

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

one two four five six
       |
     three


one two foo four five six

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

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

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

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

Shell script - поиск и замена текста в нескольких файлах с использованием списка строк

Answer 1

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

Вот пример:

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

2. Выберите один из этих двух, чтобы получить 'foo bar' в результате:

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

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

3. Вставьте «три» обратно в шаг 2, получив строку «foo bar»

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

псевдокод:

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.

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