To pytanie jest rozszerzeniem sprawdzania, czy słowa są izomorfami, i kopiuje pierwszą jego część, aby podać definicję izomorfu.

Dwa słowa są izomorfami, jeśli mają ten sam wzór powtarzania liter. Na przykład, zarówno ESTATEi DUELEDmają wzórabcdca

ESTATE
DUELED

abcdca

ponieważ litery 1 i 6 są takie same, litery 3 i 5 są takie same i nic więcej. Oznacza to również, że słowa są powiązane szyfrem podstawienia, tutaj z dopasowaniem E <-> D, S <-> U, T <-> E, A <-> L.

Biorąc pod uwagę dwa ciągi X i Y, przy czym X nie jest dłuższy niż Y, zadaniem jest ustalenie, czy istnieje podłańcuch Y, który jest izomorfem z X.

Dane wejściowe: Dwa niepuste ciągi liter od a..zA..Z, z których jeden ciąg w linii. Będzie pochodził ze standardowego wejścia.

Wyjście Podłańcuch drugiego łańcucha, który jest izomorfem z pierwszym łańcuchem, jeśli coś takiego istnieje. W przeciwnym razie wpisz „Nie!”.

Reguły Twój kod musi działać w czasie liniowym na całej długości danych wejściowych.

Wynik Twój wynik to liczba bajtów w kodzie. Wygrywa najmniej bajtów.

Przykładowe wejście i wyjście

adca
ddaddabdaabbcc

dabd

Wskazówka

Istnieje co najmniej jeden nie , że skomplikowane, szybkie i praktycznie liniowy czas rozwiązanie tego problemu.

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 z 0 statusem wyjścia)

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

Algorytm jest odmianą KMP, z wykorzystaniem testu indeksowego do dopasowywania znaków. Podstawową ideą jest to, że jeśli otrzymamy niedopasowanie pozycji X[i], możemy wrócić do następnego możliwego miejsca meczu zgodnie z najdłuższym sufiksem, X[:i]który jest izomorficzny do przedrostka X.

Pracując od lewej do prawej, przypisujemy każdemu znakowi indeks równy odległości do ostatniego poprzedniego wystąpienia tego znaku, lub jeśli nie było wcześniejszego wystąpienia, bierzemy długość bieżącego prefiksu łańcucha. Na przykład:

MISSISSIPPI
12313213913

Aby sprawdzić, czy dwa znaki pasują do siebie, porównujemy indeksy, odpowiednio dostosowując indeksy, które są większe niż długość bieżącego (pod) łańcucha.

Algorytm KMP staje się nieco uproszczony, ponieważ nie możemy uzyskać niedopasowania pierwszego znaku.

Ten program generuje pierwsze dopasowanie, jeśli takie istnieje. Używam błędu środowiska wykonawczego, aby wyjść w przypadku dopasowania, ale kod można łatwo zmodyfikować, aby wyjść czysto kosztem niektórych bajtów.

Uwaga: Do obliczania indeksów możemy użyć str.rfind(w przeciwieństwie do mojego wcześniejszego podejścia ze słownikiem) i nadal mieć liniową złożoność, zakładając, że str.rfindzaczyna się wyszukiwanie od końca (co wydaje się jedynym rozsądnym wyborem implementacji) - dla każdego znaku w alfabecie , nigdy nie musimy dwukrotnie przechodzić przez tę samą część łańcucha, więc istnieje górna granica porównań (rozmiar alfabetu) * (rozmiar łańcucha).

Ponieważ kod został dość zaciemniony w trakcie gry w golfa, oto wcześniejsze (293 bajtowe) rozwiązanie, które jest nieco łatwiejsze do odczytania:

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

Do etestów czynnościowych równoważności znaków. execInstrukcja przypisuje indeksy i robi pewne zmienne Initialisations. Pierwsza pętla przetwarza Xwartości rezerwowe, a druga pętla wyszukuje ciąg znaków.

Aktualizacja: Oto wersja, która kończy się czysto, kosztem jednego bajtu:

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 bajtów

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

Nadal jest to w większości niezamierzone, ale myślę, że powinno działać. Podstawowym algorytmem jest KMP , plus dodatkowy czynnik, który ma wpływ na wielkość alfabetu (co jest w porządku, ponieważ alfabet jest stały). Innymi słowy, jest to / powinien być jeden całkowicie niepraktyczny algorytm liniowy.

Oto kilka adnotacji, które pomogą w analizie:

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

Do testowania możesz zastąpić smniejszym alfabetem niż string.ascii_letters.

APL (Dyalog) , 32 bajty

Jest to funkcja poprawki, która przyjmuje X jako lewy argument, a Y jako prawy argument.

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

Wypróbuj online!

{… } Anonimowa lambda gdzie ⍺i ⍵reprezentują argumenty (X i Y)

 ⍳⍨⍺ ɩ ndex selfie X ( ɩ ndices pierwszego wystąpienia elementów X w X)

 ⊂ załącz, abyśmy mogli wyszukać cały wzór

 (… )⍳ Ɩ ndex pierwszego wystąpienia tego w…

  ≢⍺ tally (długość) X

  ⍵,/⍨ wszystkie podciągi tej wielkości Y (l. redukcja konkatenacji tych, ale to nie jest operacja)

  s← przechowuj w s(dla s )

  ⍳⍨¨ ɩ ndex selfie każdego z tych

 teraz mamy indeks pierwszego wzorca lub 1 + liczbę wzorców, jeśli nie znaleziono dopasowania

 (… )⊃⍨ Użyj tego indeksu, aby wybrać z…

  ⊂'No!' załączony ciąg (tak, aby działał jako pojedynczy element)

  s, z dodatkiem s