Ну самое простое решение: посчитать хеши строк, чтобы быстро все сравнивать. Теперь проверим подойдет ли нам позиция p. Для этого бинарным поиском найдем максимальную длину префикса строки t, совпадающей с префиксом строки s[p..]. Пусть эта длина равна l. Нам осталось убедится, что символ s[p+l] != t[l] (индексация с нуля), s[p+l+k] != t[l+k], и с помощью хешей проверить совпадение 2 подстрок (суффикса строки t и серединки строки t). Получим решение за O(|s| * log(|s|) + |t|). С помощью Z-функции можно получить решение за время O(|s| + |t|).