Я беру ввод от пользователя и его строку с определенной подстрокой, которая повторяется через всю строку. Мне нужно вывести подстроку или период ее длины AKA.
Скажите
S1 = AAAA // substring is A
S2 = ABAB // Substring is AB
S3 = ABCAB // Substring is ABC
S4 = EFIEFI // Substring is EFI
Я мог бы начать с Single char и проверить, совпадает ли он с его следующим символом, если это не так, я мог бы сделать это с двумя символами, а затем с тремя и так далее. Это было бы O (N ^ 2) algo. Мне было интересно, есть ли более элегантное решение для этого.
Вы можете сделать это в линейном времени и постоянном дополнительном пространстве, индуктивно вычисляя период каждого префикса строки. Я не могу вспомнить детали (есть несколько вещей, которые можно понять правильно), но вы можете найти их в Разделе 13.6 “Алгоритмы текста” Крочемора и Риттера в function Per(x).
Позвольте мне предположить, что длина строки n не меньше, чем период p.
Алгоритм
- Пусть
m= 1 иSвся строка - Возьмем
m= m * 2- Найти следующее вхождение подстроки S [: m]
- Пусть
k– начало следующего вхождения - Проверить, что S [: k] – это период
- если не перейти к 2.
Пример
Предположим, что у нас есть строка
CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC
Для каждой мощности m из 2 мы находим повторения первых символов 2^m. Затем мы распространим эту последовательность на второе вхождение. Пусть начинается с 2 ^ 1, поэтому CD.
CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC
CDCD CDCD CDCD CDCD CD
Мы не расширяем CD, так как следующее возникновение сразу после этого. Однако CD не является подстрокой, которую мы ищем, поэтому возьмите следующую мощность: 2^2 = 4 и подстроку CDCD.
CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC
CDCD CDCD
Теперь добавим нашу строку к первому повторению. Получаем
CDCDFBF
проверяем, является ли это периодическим. Это не значит, что мы идем дальше. Попробуем 2 ^ 3 = 8, поэтому CDCDFBFC
CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC
CDCDFBFC CDCDFBFC
мы пытаемся продолжить, и получим
CDCDFBFCDCDFDF
и это действительно наш период.
Я ожидаю, что это сработает в O (n log n) с некоторым алгоритмом, подобным KMP, для проверки того, где отображается данная строка. Обратите внимание, что некоторые краевые случаи все же должны быть разработаны здесь.
Интуитивно это должно сработать, но моя интуиция не удалась однажды по этой проблеме, поэтому, пожалуйста, исправьте меня, если я ошибаюсь. Я попытаюсь выяснить доказательство.
Очень приятная проблема.
Вы можете построить дерево суффиксов для всей строки в линейном времени (дерево суффикса легко найти в Интернете), а затем рекурсивно вычислить и сохранить количество листьев суффикса (вхождения префикса суффикса) N (v) ниже каждого внутреннего node v дерева суффикса. Также рекурсивно вычислить и сохранить длину каждого префикса суффикса L (v) в каждом node дерева. Затем во внутреннем node v в дереве префикс суффикса, закодированный в v, является повторяющейся подпоследовательностью, которая генерирует вашу строку, если N (v) равна общей длине строки, деленной на L (v).
Хорошо, если каждый символ входной строки является частью повторяющейся подстроки, тогда все, что вам нужно сделать, это сохранить первый символ и сравнить его с остальными символами строки один за другим. Если вы найдете совпадение, строка до тех пор, пока не будет согласована, будет вашей повторяющейся строкой.
Я тоже искал оптимально-временное решение этой проблемы. Похоже, что принятый ответ tmyklebu, по сути, таков, но я хотел бы предложить некоторое объяснение того, о чем оно на самом деле и некоторые дальнейшие выводы.
Во-первых, этот вопрос, предложенный мной, предлагает, казалось бы, многообещающее, но неправильное решение, с примечаниями о том, почему оно некорректно: корректен ли этот алгоритм для нахождения периода строки?
В общем, проблема “найти период” эквивалентна “найти шаблон внутри себя” (в некотором смысле ” strstr(x+1,x) “), но без ограничений, соответствующих после ее окончания. Это означает, что вы можете найти период, взяв любой алгоритм сопоставления строк слева направо и применив его к себе, рассматривая частичное совпадение, которое совпадает с концом стога/текста, и требования к времени и пространству так же, как и в любом алгоритме сопоставления строк, который вы используете.
Подход, процитированный в ответе tmyklebu, по существу, применяет этот принцип к сопоставлению строк в упорядоченных алфавитах, также объясняется здесь Другое оптимальное во времени и пространстве решение должно быть возможно с использованием алгоритма GS.
К сожалению, довольно известный и простой двусторонний алгоритм (также описанный здесь) не является решением, поскольку он не слева направо. В частности, улучшение после несоответствия в левом множителе зависит от того, был ли правый фактор совпадением, и невозможность другого совпадения с правильным множителем по модулю периода правильного множителя. При поиске шаблона внутри себя и игнорировании всего, что находится за его концом, мы не можем сделать вывод о том, как скоро может произойти следующее совпадение правильного фактора (часть или весь правильный фактор могли сместиться за конец шаблона), и поэтому сдвиг, который сохраняет линейное время, не может быть сделан.
Конечно, если рабочее пространство доступно, можно использовать ряд других алгоритмов. KMP является линейно-временным с O (n) пространством, и может быть возможно адаптировать его к чему-то еще достаточно эффективному только с логарифмическим пространством.