Найти подстроку, которая создает целую строку путем повторения

Question

У меня есть строка «hrhrhrhrhr».

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

В этом примере я могу сделать строку «hrhrhrhrhr» четырьмя временными добавлениями «hr» с собой.

Как найти этот подстрока? Пример лисы, «abcabcabc», тогда «abc» - это ответ.

"ttttttt" -> "t" - ответ.

«abcd» -> «abcd» - это ответ.

какой алгоритм или конкретный метод я должен использовать?

Answer 1

Я предлагаю вам взглянуть на алгоритмы поиска строк/поиска. В частности, если вы используете алгоритм KMP (Knuth-Morris Pratt) для поиска самой строки, таблица поиска даст шаблон. Кроме того, наибольшее число в таблице даст вам конечный символ подстроки, которую вы ищете (если строка действительно состоит из повторения одной подстроки).