О поиске вложений слов Зимина в произвольные слова

Abstract

Слова Зимина представляют собой универсальные неизбежные слова: любое достаточно длинное слово над любым алфавитом содержит гомоморфный образ любого фиксированного слова Зимина и произвольное неизбежное слово гомоморфно вкладывается в подходящее слово Зимина. В работе предложен квадратичный в среднем алгоритм поиска гомоморфного образа максимально возможного слова Зимина в произвольном слове.

Zimin words are the universal unavoidable ones, that is, any long enough word over any alphabet contains a morphic image of any fixed Zimin word, while any unavoidable word has a morphic image which is a factor of an appropriate Zimin word. We exhibit a quadratic on average algorithm that finds a morphic image of the maximum possible Zimin word in a given word.