Один из вариантов - использование Z-алгоритма (описанного у Гасфилда). Алгоритм для входной строки строит массив z, такой что z[i] - максимальная длина совпадения строки z[i...] со строкой z[0...]
Нужно первую строку приклеить в конец второй, применить z-алгоритм, а затем найти максимальное значение z[i], лежащее во второй строке и равное остатку её длины.
