Esta pregunta es una extensión de Verificar si las palabras son isomorfos y copia la primera parte para dar la definición de un isomorfo.

Dos palabras son isomorfos si tienen el mismo patrón de repeticiones de letras. Por ejemplo, ambos ESTATEy DUELEDtienen patrónabcdca

ESTATE
DUELED

abcdca

Como las letras 1 y 6 son iguales, las letras 3 y 5 son iguales, y nada más. Esto también significa que las palabras están relacionadas por un cifrado de sustitución, aquí con la coincidencia E <-> D, S <-> U, T <-> E, A <-> L.

Dadas dos cadenas X e Y, con X no más largo que Y, la tarea es determinar si hay una subcadena de Y que es un isomorfo con X.

Entrada: Dos cadenas de letras no vacías de a..zA..Z que una cadena por línea. Esto vendrá de la entrada estándar.

Salida Una subcadena de la segunda cadena que es un isomorfo con la primera cadena, si existe tal cosa. De lo contrario, salga "¡No!".

Reglas Su código debe ejecutarse en tiempo lineal en la longitud total de la entrada.

Puntaje Su puntaje es el número de bytes en su código. Pocos bytes ganan.

Ejemplo de entrada y salida

adca
ddaddabdaabbcc

dabd

Propina

Hay al menos una solución de tiempo no tan complicada, prácticamente rápida y lineal para este problema.

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 con 0 estado de salida)

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!'

El algoritmo es una variación de KMP, utilizando una prueba basada en índices para la coincidencia de caracteres. La idea básica es que si obtenemos un desajuste en la posición, X[i]entonces podemos recurrir al siguiente lugar posible para una coincidencia de acuerdo con el sufijo más largo X[:i]que sea isomorfo a un prefijo de X.

Trabajando de izquierda a derecha, asignamos a cada carácter un índice igual a la distancia a la ocurrencia anterior más reciente de ese carácter, o si no hay una ocurrencia previa, tomamos la longitud del prefijo de cadena actual. Por ejemplo:

MISSISSIPPI
12313213913

Para probar si dos caracteres coinciden, comparamos los índices, ajustándolos apropiadamente para los índices que son mayores que la longitud de la (sub) cadena actual.

El algoritmo KMP se simplifica un poco, ya que no podemos obtener una falta de coincidencia en el primer carácter.

Este programa genera la primera coincidencia si existe. Utilizo un error de tiempo de ejecución para salir en caso de una coincidencia, pero el código se puede modificar fácilmente para salir limpiamente a costa de algunos bytes.

Nota: Para los índices de computación, podemos usar str.rfind(a diferencia de mi enfoque anterior usando un diccionario) y aún tener una complejidad lineal, suponiendo que str.rfindcomience a buscar desde el final (que parece la única opción de implementación sensata), para cada carácter del alfabeto , nunca tenemos que atravesar la misma parte de la cadena dos veces, por lo que hay un límite superior de (tamaño del alfabeto) * (tamaño de la cadena) comparaciones.

Dado que el código se ofuscó bastante en el curso de golf, aquí hay una solución anterior (293 bytes) que es un poco más fácil de leer:

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!'

La efunción prueba la equivalencia de caracteres. La execdeclaración asigna índices y realiza algunas inicializaciones variables. El primer bucle procesa los Xvalores de retroceso y el segundo bucle realiza la búsqueda de cadenas.

Actualización: Aquí hay una versión que sale limpiamente, a costa de un byte:

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 bytes

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!")

Esto sigue siendo en su mayoría sin golf, pero creo que debería funcionar. El algoritmo central es KMP , más un factor adicional que es factorial en el tamaño del alfabeto (lo cual está bien, ya que el alfabeto es constante). En otras palabras, este es / debería ser un algoritmo lineal completamente poco práctico.

Aquí hay algunas anotaciones para ayudar con el análisis:

# 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!")

Para las pruebas, puede reemplazar scon un alfabeto más pequeño que string.ascii_letters.

APL (Dyalog) , 32 bytes

Esta es una función infija, tomando X como argumento izquierdo e Y como argumento derecho.

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

Pruébalo en línea!

{… } Lambda anónima donde ⍺y ⍵representan los argumentos (X e Y)

 ⍳⍨⍺ ɩ ndex selfie de X ( Ɩ ndices de la primera aparición de elementos de X en X)

 ⊂ adjuntar para que podamos buscar todo ese patrón

 (... )⍳ ɩ índice de la primera aparición de eso en ...

  ≢⍺ cuenta (longitud) de X

  ⍵,/⍨ todas las subcadenas de ese tamaño de Y (literalmente, reducción de concatenación de esas, pero eso es un no-op)

  s← almacenar en s(para s ubstrings)

  ⍳⍨¨ ɩ ndex selfie de cada uno de aquellos

 ahora tenemos el índice del primer patrón, o 1 + el número de patrones si no se encontró coincidencia

 (... )⊃⍨ usa ese índice para elegir ...

  ⊂'No!' la cadena incluida (para que funcione como un solo elemento)

  s, antepuesto con s