Esta questão é uma extensão do Verificar se as palavras são isomorfas e copia a primeira parte para fornecer a definição de isomorfia.

Duas palavras são isomorfos se tiverem o mesmo padrão de repetições de letras. Por exemplo, ambos ESTATEe DUELEDtêm padrãoabcdca

ESTATE
DUELED

abcdca

porque as letras 1 e 6 são iguais, as letras 3 e 5 são iguais e nada mais. Isso também significa que as palavras são relacionadas por uma cifra de substituição, aqui com a correspondência E <-> D, S <-> U, T <-> E, A <-> L.

Dadas duas cadeias X e Y, com X não mais que Y, a tarefa é determinar se existe uma subcadeia de Y que é um isomorfo com X.

Entrada: Duas seqüências de letras não vazias de a..zA..Z, uma sequência por linha. Isso virá da entrada padrão.

Saída Uma substring da segunda string, que é um isomorfo com a primeira string, se existir. Caso contrário, imprima "Não!".

Regras Seu código deve ser executado em tempo linear no comprimento total da entrada.

Pontuação Sua pontuação é o número de bytes no seu código. Menos bytes ganha.

Exemplo de entrada e saída

adca
ddaddabdaabbcc

dabd

Gorjeta

Existe pelo menos uma solução de tempo não tão complicada, praticamente rápida e linear para esse 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 com status de saída 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!'

O algoritmo é uma variação do KMP, usando um teste baseado em índice para correspondência de caracteres. A idéia básica é que, se tivermos uma incompatibilidade na posição X[i], podemos voltar ao próximo local possível para uma partida, de acordo com o sufixo mais longo X[:i]que é isomórfico para um prefixo de X.

Trabalhando da esquerda para a direita, atribuímos a cada caractere um índice igual à distância para a ocorrência anterior mais recente desse caractere, ou, se não houver ocorrência anterior, assumimos o comprimento do prefixo da string atual. Por exemplo:

MISSISSIPPI
12313213913

Para testar se dois caracteres correspondem, comparamos os índices, ajustando-os adequadamente para índices maiores que o comprimento da (sub) sequência atual.

O algoritmo KMP se torna um pouco simplificado, pois não podemos obter uma incompatibilidade no primeiro caractere.

Este programa gera a primeira correspondência, se houver. Uso um erro de tempo de execução para sair no caso de uma correspondência, mas o código pode ser facilmente modificado para sair de forma limpa, ao custo de alguns bytes.

Nota: Para índices de computação, podemos usar str.rfind(em oposição à minha abordagem anterior usando um dicionário) e ainda ter complexidade linear, supondo que str.rfindcomece a pesquisar a partir do final (que parece a única opção de implementação sensata) - para cada caractere no alfabeto , nunca precisamos percorrer a mesma parte da string duas vezes, para que haja um limite superior das comparações (tamanho do alfabeto) * (tamanho da string).

Como o código ficou ofuscado durante o golfe, eis uma solução anterior (293 bytes) que é um pouco mais fácil de ler:

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

A efunção testa a equivalência de caracteres. A execinstrução atribui índices e faz algumas inicializações variáveis. O primeiro loop processa os Xvalores de retorno e o segundo loop faz a pesquisa de cadeias.

Atualização: Aqui está uma versão que sai corretamente, ao custo de um 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!")

Isso ainda é praticamente não-destruído, mas acho que deve funcionar. O algoritmo principal é o KMP , mais um fator adicional que é fatorial no tamanho do alfabeto (o que é bom, pois o alfabeto é constante). Em outras palavras, esse é / deveria ser um algoritmo linear completamente impraticável.

Aqui estão algumas anotações para ajudar na análise:

# 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 testar, você pode substituir spor um alfabeto menor que string.ascii_letters.

APL (Dyalog) , 32 bytes

Esta é uma função infix, considerando X como argumento à esquerda e Y como argumento à direita.

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

Experimente online!

{… } Lambda anônima onde ⍺e ⍵representa os argumentos (X e Y)

 ⍳⍨⍺ ɩ NDEX selfie de X ( Ɩ ndices da primeira ocorrência de elementos de X em X)

 ⊂ coloque para que possamos procurar por todo esse padrão

 (… )⍳ Índice da primeira ocorrência disso em…

  ≢⍺ registro (comprimento) de X

  ⍵,/⍨ todas as substrings desse tamanho de Y (redução de concatenação dessas, mas isso não é uma operação)

  s← armazenar em s(para s ubstrings)

  ⍳⍨¨ ɩ NDEX selfie de cada um daqueles

 agora temos o índice do primeiro padrão, ou 1 + o número de padrões, se nenhuma correspondência foi encontrada

 (… )⊃⍨ Use esse índice para escolher…

  ⊂'No!' a cadeia incluída (para que funcione como um único elemento)

  s, anexado com s