Как найти все грани строки

Время на прочтение
8 мин

Количество просмотров 19K

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

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

Скажу сразу, что данный материал написан для таких же обывателей как я, и что я понимаю, что на Хабре была написаны некоторые статьи по поводу алгоритмов обработки строк и была даже пара статей про КМП. Но со своей стороны я хочу максимально просто разжевать устройство этого алгоритма, замерить его производительность и посмотреть где, когда и для чего его можно использовать. В общем, я считаю мне есть что сказать.

Код, примеры и термины будут местами из ранее упомянутой книги С. Окулова «Алгоритмы обработки строк», так что, если какой-то термин будет упомянут не правильно, то милости прошу, поправляйте и я внесу коррективы.

Устройство алгоритма

Грани строки

Начать стоит с того, что у строки есть грани. Гранью строки называется любой префикс строки, который равен ее суффиксу.

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

Таким образом для строки aaaaa, грани будут a, aa, aaa, aaaa, но aaaaa гранью не будет.
К чему собственно разгон: с помощью вычисления массива граней (он же таблица префиксов и суффиксов) реализуется главная фишка алгоритма — таблица сдвигов паттерна поиска.

Таблица сдвигов паттерна поиска

Есть например у нас паттерн поиска abaaba.

1. Берем первый символ строки (а) и ищем для него грань. Так как для него грани быть не может (потому что грань не может быть равна строке) то грань — 0.
2. Берем теперь два первых символа (ab) и ищем грань для них. Так как нет суффикса, который равен префиксу, то грань снова 0.
3. Берем подстроку aba и ищем максимальную грань для нее. Так как из префиксов и суффиксов совпадают только буквы «а», то максимальная грань — 1.

Повторять до конца.

export function findBorders(pattern: string): number[] {
    const borders = new Array(pattern.length);
    borders[0] = 0;

    let currentIndex = 0;

    for (var i = 1; i < pattern.length; i++) {
        while (currentIndex > 0 && pattern[currentIndex] !== pattern[i]) {
            currentIndex = borders[currentIndex - 1];
        }

        if (pattern[currentIndex] === pattern[i]) {
            currentIndex++;
        }

        borders[i] = currentIndex;
    }

    return borders;
}

UPD: спасибо wataru, за то что указал более оптимальный метод поиска граней.

Результат должен быть вот такой:

Для чего были нужны все эти манипуляции? Сейчас поясню.

Массив граней это градообразующее предприятие всего алгоритма: его задача сказать нам, откуда продолжать сравнивать, если вдруг наш процесс сравнения строки собьется.

Ход поиска

Что здесь происходит:
Мы сравниваем наш текст T с паттерном P. Первые два символа текста совпали с паттерном, но третий символ T и P не совпали (T[2] != P[2]). Значит смотрим в наш массив граней br. Ага, грань br[2] имеет длину 0. Значит сдвигаем P на 2 символа вправо (длина совпавшего участка за вычетом длины грани плюс сдвиг на единичку: 2 - 1 + 1).

Передвинули, проверяем символ еще раз:T[2] != P[0], хорошо, тогда сдвигаем паттерн еще на 0 - 0 + 1.

Дальше совпадает еще три символа и так далее.

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

export function getSubstringKMP(text: string, pattern: string): number[] {
    const borders = findBorders(pattern);
    const result = [];

    let compareIndex = 0;

    for (let i = 0; i < text.length; i++) {
        while (compareIndex > 0 && text[i] !== pattern[compareIndex]) {
            compareIndex = borders[compareIndex - 1];
        }

        if (text[i] === pattern[compareIndex]) {
            compareIndex++;
        }

        if (compareIndex === pattern.length) {
            result.push(i - compareIndex + 1);
            compareIndex = borders[pattern.length - 1];
        }
    }

    return result;
}

Замеры производительности

Сравним производительность наивного алгоритма и нашей реализации КМП.

Текст:

Паттерн:
GTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTA

Замер происходит для всех четырех вхождений.

getSubstringNaive x 2,961 ops/sec ±1.57% (88 runs sampled)
getSubstringKMP x 83,890 ops/sec ±0.48% (93 runs sampled)

Выходит так, что КМП быстрее почти в 27 раз.

Напомню, что наивный алгоритм сравнивает последовательность в строке с паттерном полностью, то есть, если в какой-то момент он видит, что происходит несовпадение, то он все равно сравнивает до конца, надеясь на чудо. Ну выходит, что это тупой алгоритм, а не наивный.

export function getSubstringNaive(text: string, pattern: string): number[] {
    const result = [];

    for (let i = 0; i <= text.length - pattern.length; i++) {
        let flag = true;
        // Ну о-о-о-очень наивный алгоритм
        for (let j = 0; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                flag = false;
            }

            if (j === pattern.length - 1 && flag) {
                result.push(i);
            }
        }
    }

    return result;
}

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

export function getSubstringNotSoNaive(text: string, pattern: string): number[] {
    const result = [];

    for (let i = 0; i <= text.length - pattern.length; i++) {
        for (let j = 0; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                break;
            }

            if (j === pattern.length - 1) {
                result.push(i);
            }
        }
    }

    return result;
}

Повторим наши замеры:

getSubstringNaive x 2,984 ops/sec ±0.75% (97 runs sampled)
getSubstringKMP x 89,802 ops/sec ±0.20% (94 runs sampled)
getSubstringNotSoNaive x 109,839 ops/sec ±0.52% (96 runs sampled)

И вот мы в 1.2 раза обогнали КМП алгоритм.

Сравнение продуктивности

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

Код для всего этого безобразия будет выглядеть

export class Counter {
    public get count(): number {
        return this._count;
    }

    public readonly name: string;
    private _count: number = 0;

    public constructor(name: string) {
        this.name = name;
    }

    public increase(): void {
        this._count++;
    }
}

const counterMap = new Map<string, Counter>();

export function createCounter(name: string): Counter {
    const counter = new Counter(name);

    counterMap.set(name, counter);

    return counter;
}

export function getAllCounters(): [string, Counter][] {
    return Array.from(counterMap.entries());
}

export function compare<T>(first: T, second: T, counter: Counter): boolean {
    counter.increase();

    return first === second;
}

Засунем везде функцию compare и будем считать каждое фактическое сравнение символов.

Результат:

getSubstringNaive: 36,556
getSubstringKMP: 1,422
getSubstringNotSoNaive: 1,434

У КМП результат по количеству сравнений наименьший, ему в спину дышит не очень наивный алгоритм с разницей всего в 12 сравнений, а полный аутсайдер — наивный алгоритм.

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

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

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

Найдем все упоминания слов:

1. дуб
2. Андрей
3. обломанн

Результаты

Ops/sec

Количество сравнений

Очевидные и не очень выводы

Первый вывод и он же очевидный: чем больше сравнений, тем меньше скорость алгоритма.

Второй: КМП и не очень наивный алгоритм имеют практически одинаковое количество сравнений, но при этом разница в скорости примерно 35%.

Давайте поподробнее

Длина текста — 1673 символа. Мы фактически подтвердили сложность алгоритмов (хотя это от нас и не требовалось и не то чтобы кто-то в ней сомневался, но мне все равно приятно), потому что у наивного алгоритма количество сравнений изменяется примерно как n * m, а у остальных алгоритмов оно с определенной погрешностью держится около n, как и задумано.

Разница между КМП и не очень наивным алгоритмом такая большая оттого, что у КМП есть препроцессинг строки, а у его оппонента его нет. Кроме того, у КМП есть еще и накладные расходы на проверки массива граней, на входы и выходы из различных циклов и if’ов, но так как почти во всех случаях массив граней пустой, то получается, что порядок сравнений у обоих алгоритмов практически идентичный.

Но, внезапный твист: главная фишка этого алгоритма не скорость, а то, что он не делает повторных сравнений уже пройденных символов. Если вы сравните алгоритмы, то наивная и не очень реализации сравнивают строки посимвольно и при несовпадении передвигают индекс сравнения вперед и идут по новой смотреть уже проверенные символы, а КМП видит несовпадение и перекидывает индекс сравнения в соответствии с массивом граней и идет себе дальше.

Это значит, что если у нас есть огромный файл генома и условно старый компьютер с ограниченным размером оперативной памяти (а КМП был опубликован в 1977 году, когда компьютер стоил как ракета, а оперативной памяти в них было с гулькин нос), то мы можем постепенно считывать этот файл (или перфоленту) и в реальном времени сравнивать поступающие данные и нужной последовательностью.

Вывод

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

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

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

Здравствуйте такой вопрос еть алгоритм вот его псевдокод взят из книги «Методы и алгоритмы на строках. Билл Смит»:

B[1]<-0 //Массив с гранями
for(i<-1 to n-1 do
   b<-B[b]
if(x[i+1]=x[b+1]
then B[i+1]<-b+1
else
B[i+1]<-0

вот с++ реализация

void SetBorder(std::string & text,std::vector<int> &border)
{
    border.resize(text.size());
    border[1]=0;
    int k=0;
    for(int i=1;i<text.size()-1;++i)
    {
        k=border[i];
        while (k>0&&text[k+1]!=text[i+1])
        {
            k=border[k];
        }
        if(text[k+1]==text[i+1])
        {
            border[i+1]=k+1;
        }
        else
        {
            border[i+1]=0;
        }
    }
}

Почему то не правильно работает, не подскажите вчем может быть ошибка

1. Классические алгоритмы решения задачи точного совпадения

Примитивный алгоритм имеет временную
сложность O(n∙m).
Суть всех последних достижений (конец 20 века и
по настоящее время) – разработка алгоритмов с
временной сложностью O(n+m).
Основа, ключевой момент, предварительный
анализ исходных данных (препроцессинг) с целью
выявления
неких
закономерностей
в
них,
позволяющих решать основную задачу за указанное
время. Естественно, что алгоритм препроцессинга
должен иметь линейную временную оценку.

2.

Грани строки
Определение. Гранью (border, verge, brink) br строки S
называется любой собственный префикс этой строки,
равный суффиксу S.
Строка S=abaababaabaab имеет две грани (не пустые)
ab и abaab. Строка S=abaabaab также имеет две грани ab и
abaab, но вторая грань перекрывающаяся. Строка длины n
из повторяющегося символа, например aaaaaaaa (a8), имеет
n-1 грань. Для S=a8 это грани: a, aa, aaa, aaaa, aaaaa,
aaaaaa и aaaaaaa. Понятие «собственный» префикс
исключает грань, совпадающую с самой строкой. Длина
грани это количество символов в ней. Естественным
обобщением
понятия
«грань»
является
понятие
«наибольшей грани» – наибольший (по количеству
символов) собственный префикс строки, равный её
суффиксу.

3.

Простым алгоритмом вычисления наибольшей
грани строки S является последовательная проверка
совпадения префиксов S[1], S[1..2], S[1..3], …, S[1..n1] с соответствующими суффиксами S[n], S[n-1..n],
S[n-2..n], …, S[2..n].
функция maxBorder(S)
n←длина(S)
br←0
для i от 1 до n-1: {Цикл
j←n-i+1
по длине грани.}
пока (j≤n) и (S[i+j-n]=S[j]):j←j+1
если j=n+1:br←i
вернуть br
2
Временная сложность алгоритма O(n ).

4.

Вычисление значений наибольших граней для
всех подстрок S[1..i] (i=1..n) – в массив br[1..n].
Значение br[1] равно 0, ибо подстрока S[1] не имеет
собственных подстрок. Последовательное применение
предыдущей логики к каждой подстроке приводит к
алгоритму с временной сложностью O(n3).
процедура maxBorderArray(S)
n←длина(S)
br[1]←0
для i от 2 до n:
br[i]←maxBorder(подстрока S(1,i))

5.

Примеры br для различных строк S.
№
1
2
3
4
5
S
aaaaaa
abcdef
abaababaabaab
abcabcabcabc=(abc)4
abcabdabcabeabcabdabcabc
br
0, 1, 2, 3, 4, 5
0, 0, 0, 0, 0, 0
0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 4, 5
0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 0, 0, 1, 2, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 3
Какие наблюдения можно сделать на основании этих
данных? Во-первых, br[i+1] ≤ br[i]+1 для любых i от 1 до n-1
и если значения элементов br возрастают, то они возрастают
с шагом 1. Когда br[i+1] = br[i]+1? Ответ однозначен – при
S[i+1] = S[br[i]+1]. Если символ S в позиции i+1 совпадает с
символом, следующим за максимальным префиксом S[1..i]
совпадающим с суффиксом S[1..i], то наибольшая грань
br[i+1] для S[1..i+1] просто увеличивается на 1. А если
S[i+1] ≠ S[br[i]+1]? Ситуация для строки S[1..12] третьего
примера поясняется на рис. 1а, а для строки S[1..24] пятого
примера из табл. 1.1 – на рис. 1б.

6.

1234567890123
abaababaabaab
br 0 0 1 1 2 3 2 3 4 5 6 4 5
123456789012345678901 2 3 4
abcabdabcabeabcabdabc a b c
br 0 0 0 1 2 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 3
S[12]≠S[7], но S[12]=S[4],
следовательно, br[12]=br[6]+1
S[24]≠S[12], S[24]≠S[6], но S[24]=S[3],
следовательно, br[24]=br[5]+1
a
б
Рис. 1. Примеры вычислений значений br при S[i+1]≠S[br[i]+1]

7.

Временные параметры алгоритма. Цикл For выполняется n-1
раз. Количество шагов вложенного цикла While различно. Время
выполнения алгоритма пропорционально общему количеству
присваиваний значений переменной t. Оно равно n-1 (в цикле For),
плюс число этих операций внутри цикла While. В цикле While
происходит уменьшение значения переменной t. На каждой же
итерации For значение t, а оно всегда неотрицательное, или остается
равным нулю, или увеличивается на единицу. Таким образом,
количество увеличений пропорционально (n-1), но общее
количество уменьшений в цикле While, а оно всегда осуществляется
не менее, чем на 1, не может превосходить количества увеличений.
Следовательно, t изменяется внутри цикла While не более (n-1) раза
и полное число присваиваний t ограничено сверху величиной 2(n1)=O(n). Итак, массив br для S формируется не за время O(n3), как
было рассмотрено ранее, а за время O(n).

8.

Таким образом, в массиве br фиксируются грани
всех подстрок S[1..i], i=1…n. Другими словами,
вычисляются грани всех префиксов строки S.
Аналогичную задачу можно решить и для суффиксов
строки S, например, в массиве bw сформировать
грани S[i..n], i=1..n. На рис. 2 показано, в чем
заключается отличие понятий.
S
1
i
n
i
n
а
S
1
б
Рис. 2. Грани: а) грань префикса S[1..i] – br[i]; б) грань
суффикса S[i..n] – bw[i]

9.

Пример.
1 2
S a b
br 0 0
bw 8 7
3
a
1
6
4
a
1
5
5
b
2
4
6
a
3
3
7
b
2
2
8
a
3
1
9
a
4
8
0
b
5
7
1
a
6
6
2
a
4
5
3
b
5
4
4
a
6
3
5
b
7
2
6
a
8
1
7
a
9
3
8
b
10
2
9
a
11
1
0
b
7
0
1
a
8
0
Логика формирования значений элементов
массива bw аналогична той, что рассмотрена в
процедуре MaxBorderArray.
процедура borderRigth(S)
n←длина(S)
bw[n]←0
для i от n до 2:
t←bw[i]
пока (t>0) и (S[i-1]≠S[n-t]:t←bw[n-t]
если S[i-1]=S[n-t]:bw[i-1]←t+1
иначе: bw[i-1]←0

10.

Алгоритм Д. Кнута – Дж. Морриса – В. Пратта
Дан образец (образцы). На обработку поступает текст. Требуется
выявлять вхождение образцов в текст.
Пусть требуется в T=ababcxabdabcxabcxabcde найти вхождения
P=abcxabcde. Какую информацию о P необходимо иметь, чтобы
выполнять «сдвиги» так, как это показано в таблице?
i 1 2 3
T a b a
P a b c
a
4
b
x
b
5
c
a
c
6
x
b
x
7
a
c
a
a
8
b
d
b
b
9
d
e
c
c
a
10 11 12 13 14 15 16 17 18 19 20 21 22
a b c x a b c x a b c d e
d
x
b
a
e
a
c
b
b
x
c
c
a
x
d
b
a
a
Массив граней br=(0, 0, 0, 0, 1, 2, 3, 0, 0).
e
c
b
b
d
c
c
e
d
x
e
a
b
c
d
e

11.

Пусть вычислен массив граней P. Другими словами для
каждой позиции i в P определена br[i] – длина наибольшего
собственного суффикса P[1..i], совпадающего с префиксом P.
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
P a b c a e a b c a b c a
br 0 0 0 1 0 1 2 3 4 2 3 4
a b c a e a b c a b c a
Предположим, что произошло несравнение символов при
i=9 и некоторой позиции k текста T. Значение br[8] говорит о
наличии суффикса, длиной 3, совпадающего с префиксом P. И
для того, чтобы этот префикс совпал с суффиксом, следует
сдвинуть P на 8–3=5 позиций. Гарантируется совпадение br[8]
(трех) символов P с соответствующими символами T и
следующее сравнение следует выполнять между символами T[k]
и P[br[8]+1]. В этом вся суть алгоритма – за счет знания
структуры образца P, анализ которой выполняется за линейное
время, сдвигать при поиске вхождения P в T более чем на одну
позицию. При этом символ T[k] участвовал в сравнении как
минимум два раза.

12.

Алгоритм Кнута – Морриса – Пратта
процедура solve(T,P)
n←длина(T)
m←длина(P)
maxBorderArray(P); {Вычисляем
значения элементов массива граней
br.}
q←0
для i от 1 до n:
пока (q>0) и (P[q+1]<>T[i]):q←br[q]
если P[q+1]=T[i]:q←q+1
если q=m:
вывод(вхождение P в T с позиции
i-m+1)
q←br[m]

13.

В первом примере «жирным» шрифтом выделен
случай,
дающий
основания
для
дальнейшего
усовершенствования алгоритма. На этот момент времени
сравнивается символ T[9] с P[7] (i=9, q=6). Работает цикл
While (формализованная запись) и значение q становится
равным 2 (br[6]=2). Происходит сравнение T[9] с P[3].
Результат заведомо известен, ибо P[3]=P[7], и уже было
несовпадение символа P[7] с T[9]. Затем q присваивается
значение 0 (br[2]=0) и осуществляется сравнение T[9] с P[1],
но это уже следующая строка таблицы. Как исключить эти
лишние сдвиги?
Уточним понятие грани. Для каждой позиции i строки
S определим brs[i] как длину наибольшего собственного
суффикса S[1..i], совпадающего с префиксом S, и такого,
что S[i+1]≠S[brs[i]+1]. Другими словами, следующий
символ за префиксом, равным суффиксу, не должен
совпадать с символом S[i+1].

14.

Три примера вычисления значений уточненных граней.
Естественно, что значения элементов массива brs, получены
на основе вычисленного ранее массива br.
S
br
brs
S
br
brs
S
br
brs
1
a
0
0
a
0
0
a
0
0
2
b
0
0
b
0
0
b
0
0
3
c
0
0
a
1
1
a
1
1
4
x
0
0
a
1
0
a
1
0
5
a
1
0
b
2
0
b
2
0
6
b
2
0
a
3
3
a
3
3
7
c
3
3
b
2
0
b
2
0
8
d
0
0
a
3
1
a
3
1
9
e
0
0
a
4
0
a
4
0
10 11 12 13 14 15 16 17 18
19
20 21
b
5
0
b
5
0
a
11
11
b
7
0
a
6
6
a
6
6
a
4
0
a
4
0
b
5
5
b
5
0
a
6
3
b
7
0
a
8
1
a
9
0
b
10
0
a
8
8
Примечание. Значение brs[n] получено при условии, что к S
приписывается символ, которого нет в алфавите.

Постановка задачи: Дан некий текст T и образец слова W. Необходимо найти все вхождения образца слова W в текст T.

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

        1.     Простой алгоритм решения.

Необходимо посимвольно прикладывать образец текста W к самому тексту T, начиная с первой позиции. Таким образом, возможно две ситуации: либо символы совпадут, либо не совпадут, начиная с какой-то позиции. Если символы совпали, то это совпадение фиксируется. Затем образец текста сдвигается на один символ вправо и снова начинается сравнение, при этом нет учета результата предыдущих сравнений. 

Например, пусть дан текст T = abcaabcabb и слово W = abc, то наглядо алгоритм можно представить следующим образом:

Таблица 1 – Пример работы простого алгоритма

На языке C++ алгоритм может быть реализован следующим образом:

int find_substrings(string S, string W) {

unsigned int i, j;

int number = 0;

for (i = 0; i < S.length() – W.length() + 1; i++) {

j = 0;

while ((j < W.length()) && (W[j] == S[i + j])) {

j = j + 1;

}

if (j == W.length())

{

cout << “Вхождение слова ” << W << ” , с номера позиции: ” << i << endl;

number++;

}

}

return number;

}

Здесь функция find_substrings возвращает количество вхождений подстроки в строку, а также выводит в консольное окно номера позиций, с которых начинается вхождение.

Очевидно, что временная сложность алгоритма имеет значение – O(S.length()W.length())

        2.     Алгоритм Кнута-Морисса-Пратта поиска подстроки в строке.

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

В 1970 году Д. Кнут, Д. Морис и В. Пратт пришли к идее создания алгоритма, который способен найти подстроку в строке за количество сравнений, эквивалентных длине строки. Идея алгоритма состоит в том, чтобы не прикладывать подстроку к строке со сдвигом всего в один символ, а максимально увеличить это расстояние, сократив таким образом количество сравнений.

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

Алгоритмы поиска граней в строке подробно описаны в книге С.М. Окулова [1].

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

int* max_border_array(string T) {

int i, n = T.length(), t;

int *br = new int[n];

br[0] = 0;

for (i = 1; i < n; i++) {

t = br[i — 1];

while ((t > 0) && (T[i] != T[t])) {

t = br[t — 1];

}

if (T[i] == T[t]) {

br[i] = t + 1;

} else {

br[i] = 0;

}

}

return br;

}

Перед началом работы алгоритма Кнута-Мориса-Пратта необходимо вычислить массив граней подстроки W. А затем, прикладывать подстроку к строке со сдвигом , где  – текущая позиция в слове,  —  величина грани слова в позиции .

Рассмотрим работу алгоритма на примере:

T = ababababccabdabab

W = abab

Массив граней br слова W = (0, 0, 1, 2)

Таблица 2 – Пример работы алгоритма Кнута-Мориса-Пратта

Реализация алгоритма Кнута-Мориса-Пратта на языке С++:

vector<int> KMP(string str, string sub, int* br) {

vector<int> solution;

int poz = 0;

for (int i = 0; i < str.size(); i++) {

while (poz == sub.size() || (poz > 0 && sub[poz] != str[i])) {

poz = br[poz — 1];

if (sub.size() – poz > str.size() – i)

break;

}

if (str[i] == sub[poz]) {

poz++;

}

if (poz == sub.size()) {

solution.push_back(i – poz + 1);

}

}

return solution;

}

Таким образом, временная сложность алгоритма Кнута-Мориса-Пратта – O(S.length()W.length()), что гораздо эффективнее простого алгоритма поиска подстроки в строке.

Библиографический список

1. Окулов С.М. Алгоритмы обработки строк. – М.: БИНОМ. Лаборатория знаний, 2009.
2. Семинар 13. Строки в С++. Алгоритм Кнута-Морриса-Пратта. – ВШЭ.: Построение и анализ алгоритмов, 2014.

Количество просмотров публикации: Please wait

Все статьи автора «Maria_hse»