Этот вопрос является расширением проверки, являются ли слова изоморфами, и копирует первую часть этого текста, чтобы дать определение изоморфа.

Два слова являются изоморфами, если они имеют одинаковый шаблон повторения букв. Например, оба ESTATEи DUELEDимеют шаблонabcdca

ESTATE
DUELED

abcdca

потому что буквы 1 и 6 одинаковы, буквы 3 и 5 одинаковы и ничего более. Это также означает, что слова связаны шифром замещения, здесь с соответствием E <-> D, S <-> U, T <-> E, A <-> L.

Для двух строк X и Y, причем X не длиннее Y, задача состоит в том, чтобы определить, существует ли подстрока Y, которая является изоморфной с X.

Входные данные: две непустые строки букв из a..zA..Z, по одной строке на строку. Это будет исходить из стандартного ввода.

Выходные данные Подстрока второй строки, которая является изоморфой первой строки, если такая вещь существует. В противном случае выведите «Нет!».

Правила Ваш код должен выполняться за линейное время от общей длины ввода.

Оценка Ваша оценка - это количество байтов в вашем коде. Побеждает несколько байтов.

Пример ввода и вывода

adca
ddaddabdaabbcc

dabd

Чаевые

Существует , по крайней мере один не , что сложно, практически быстро и линейное время решение этой проблемы.

Python 2, 338 326 323 321 310 306 297 293 290 289 280 279 266 264 259 237 230 229 226 223 222 220 219 217 ( 260 238 231 228 225 223 221 220 218 с 0 статусом выхода)

exec'''s=raw_input()
S=[M-s.rfind(c,0,M)for M,c in enumerate(s)]
k=0
j=x=%s
while k<=M+x:
 if S[k]>j<W[j]or S[k]==W[j]:
    k+=1;j+=1;T+=[j]
    if j-L>x:print s[k-j:k];z
 else:j=T[j]
'''*2%('-1;T=[0];W=S;L=M',0)
print'No!'

Алгоритм представляет собой вариант KMP, использующий основанный на индексе тест для сопоставления символов. Основная идея состоит в том, что если мы получим несоответствие в позиции, X[i]то мы можем вернуться к следующему возможному месту для совпадения в соответствии с самым длинным суффиксом, X[:i]который изоморфен префиксу X.

Работая слева направо, мы присваиваем каждому символу индекс, равный расстоянию до самого последнего предыдущего появления этого символа, или, если предыдущее вхождение отсутствует, мы берем длину текущего строкового префикса. Например:

MISSISSIPPI
12313213913

Чтобы проверить, совпадают ли два символа, мы сравниваем индексы, соответственно корректируя индексы, которые больше, чем длина текущей (под) строки.

Алгоритм KMP становится немного упрощенным, поскольку мы не можем получить несоответствие по первому символу.

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

Примечание: для вычисления индексов мы можем использовать str.rfind(в отличие от моего более раннего подхода с использованием словаря) и все еще иметь линейную сложность, предполагая, что str.rfindпоиск начинается с конца (что кажется единственным разумным выбором реализации) - для каждого символа в алфавите нам никогда не придется проходить одну и ту же часть строки дважды, поэтому существует верхняя граница сравнений (размер алфавита) * (размер строки).

Поскольку в ходе игры в гольф код был довольно запутан, вот более раннее (293 байтное) решение, которое немного легче читать:

e=lambda a:a>i<W[i]or a==W[i]
exec('s=raw_input();S=[];p={};M=i=0\nfor c in s:S+=[M-p.get(c,-1)];p[c]=M;M+=1\nW=S;L=M;'*2)[:-9]
T=[0]*L
k=1
while~k+L:
 if e(W[k]):i+=1;k+=1;T[k]=i
 else:i=T[i]
m=i=0
while m+i<M:
 if e(S[m+i]):
    if~-L==i:print s[m:m+L];z
    i+=1
 else:m+=i-T[i];i=T[i]
print'No!'

В eфункциональных тестах эквивалентность символов. execОператор присваивает индексы и делает некоторые переменные инициализацыми. Первый цикл обрабатывает Xзапасные значения, а второй - поиск строки.

Обновление: вот версия, которая выходит чисто, по стоимости одного байта:

r='No!'
exec'''s=raw_input()
S=[M-s.rfind(c,0,M)for M,c in enumerate(s)]
k=0
j=x=%s
while k<=M+x:
 if S[k]>j<W[j]or S[k]==W[j]:
    k+=1;j+=1;T+=[j]
    if j-L>x:r=k=s[k-j:k]
 else:j=T[j]
'''*2%('-1;T=[0];W=S;L=M',0)
print r

Python 3, 401 байт

import string,itertools
X=input()
Y=input()
x=len(X)
t=[-1]+[0]*~-x
j=2
c=0
while j<x:
 if X[j-1]==X[c]:c+=1;t[j]=c;j+=1
 elif c>0:c=t[c]
 else:t[j]=0;j+=1
s=string.ascii_letters
*b,=map(s.find,X)
for p in itertools.permutations(s):
 m=i=0
 while m+i<len(Y):
  if p[b[i]]==Y[m+i]:
   if~-x==i:print(Y[m:m+x]);exit()
   else:i+=1
  else:
   if-1<t[i]:m+=i-t[i];i=t[i]
   else:i=0;m+=1
else:print("No!")

Это до сих пор в основном не одурачено, но я думаю, что это должно работать. Основным алгоритмом является KMP , плюс дополнительный фактор, который зависит от размера алфавита (что хорошо, поскольку алфавит постоянен). Другими словами, это / должен быть один совершенно непрактичный линейный алгоритм.

Вот несколько аннотаций, которые помогут с анализом:

# KMP failure table for the substring, O(n)
t=[-1]+[0]*~-x
j=2
c=0
while j<x:
 if X[j-1]==X[c]:c+=1;t[j]=c;j+=1
 elif c>0:c=t[c]
 else:t[j]=0;j+=1

# Convert each char to its index in a-zA-Z, O(alphabet * n)
s=string.ascii_letters
*b,=map(s.find,X)

# For every permutation of letters..., O(alphabet!)
for p in itertools.permutations(s):
 # Run KMP, O(n)
 m=i=0
 while m+i<len(Y):
  if p[b[i]]==Y[m+i]:
   if~-x==i:print(Y[m:m+x]);exit()
   else:i+=1
  else:
   if-1<t[i]:m+=i-t[i];i=t[i]
   else:i=0;m+=1
else:print("No!")

Для тестирования вы можете заменить sна меньший алфавит, чем string.ascii_letters.

APL (Dyalog) , 32 байта

Это инфиксная функция, принимающая X в качестве левого аргумента и Y в качестве правого аргумента.

{(s,⊂'No!')⊃⍨(⍳⍨¨s←⍵,/⍨≢⍺)⍳⊂⍳⍨⍺}

Попробуйте онлайн!

{… } Анонимная лямбда, где ⍺и ⍵представляют аргументы (X и Y)

 ⍳⍨⍺ ɩ NDEX селфи Х ( ɩ ndices первого появления элементов X в X)

 ⊂ приложить, чтобы мы могли искать всю эту модель

 (... )⍳ Индекс первого появления этого в ...

  ≢⍺ подсчет (длина) X

  ⍵,/⍨ все подстроки этого размера Y (горит сокращение конкатенации тех, но это не является опцией)

  s← хранить в s(для з ubstrings)

  ⍳⍨¨ selfie ndex селфи каждого из этих

 теперь у нас есть индекс первого шаблона или 1 + количество шаблонов, если совпадений не найдено

 (... )⊃⍨ использовать этот индекс, чтобы выбрать из ...

  ⊂'No!' вложенная строка (чтобы она функционировала как отдельный элемент)

  s, с добавлением s