Coursera: algs4partII-001. Неделя 4. Часть 2. Substring Search

[svetasmirnova]

1. Knuth-Morris-Pratt DFA. Первоначально это задание мне показалось самым простым: нужно для каждой буквы пометить состояние, на которое нужно перемещаться на следующем шаге. Но оно же оказалось и самым сложным, потому что я пыталась делать его в уме и таким образом пропускала некоторые состояния. В результате несколько вариантов запорола. Помогло выписывать пройденный путь отдельной строкой: A B B A и т.п. В таком случае очень легко сравнить с искомой строкой и вероятность ошибки меньше.
2. Boyer-Moore algorithm. Для выполнения этого задания мне пригодился текстовый редактор: первая строка - текст, в котором искать, вторая строка - первый шаг, третья - второй и т.п. Пробелами располагаем где требуется: если знак в исходном тексте, находящийся на той же позиции, что и последний знак строки, которую мы ищем, совпадает с последним знаком - сдвигаем на одну позицию; совпадает с другим знаком в строке - совмещаем с последним нахождением этого знака; ни с чем не совпадает - сдвигаем всю строку на её длину.
3. Rabin-Karp hash function. Тут тоже всё элементарно: нужно воспользоваться формулой из слайдов. (((previous_reminder - first_sign_of_prev_sequence*( (R*num_symbols) % Q) ) * R + last_sign_of_cur_sequence) % Q + Q) % Q, где R - порядок