Check if there is an isomorph substring This question is an extension of Check if words are isomorphs  and copies the first part of it to give the definition of an isomorph.

Two words are isomorphs if they have the same pattern of letter repetitions. For example, both ESTATE and DUELED have pattern abcdca

ESTATE
DUELED

abcdca


because letters 1 and 6 are the same, letters 3 and 5 are the same, and nothing further. This also means the words are related by a substitution cipher, here with the matching E &lt;-&gt; D, S &lt;-&gt; U, T &lt;-&gt; E, A &lt;-&gt; L.

Given two strings X and Y, with X no longer than Y, the task is to determine if there is a substring of Y which is an isomorph with X.

Input: Two non-empty strings of letters from a..zA..Z which one string per line.  This will come from standard input.

Output A substring of the second string which is an isomorph with the first string, if such a thing exists. Otherwise output "No!".

Rules Your code must run in linear time in the total length of the input.

Score Your score is the number of bytes in your code.  Fewest bytes wins.



Example input and output

adca
ddaddabdaabbcc

dabd


Tip

There is at least one not that complicated, practically fast and linear time solution to this problem.
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 with 0 exit status)

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


The algorithm is a variation of KMP, using an index-based test for character matching. The basic idea is that if we get a mismatch at position X[i] then we can fall back to the next possible place for a match according to the longest suffix of X[:i] that is isomorphic to a prefix of X.

Working from left to right, we assign each character an index equal to the distance to the most recent previous occurrence of that character, or if there is no previous occurrence then we take the length of the current string prefix. For example:

MISSISSIPPI
12313213913


To test whether two characters match, we compare indices, adjusting appropriately for indices that are greater than the length of the current (sub)string.

The KMP algorithm becomes a little simplified since we cannot get a mismatch on the first character.

This program outputs the first match if one exists. I use a runtime error to exit in the event of a match, but the code can be easily modified to exit cleanly at the cost of some bytes.

Note: For computing indices, we can use str.rfind (as opposed to my earlier approach using a dictionary) and still have linear complexity, assuming that str.rfind starts searching from the end (which seems the only sane implementation choice) -- for each character in the alphabet, we never have to traverse the same part of the string twice, so there is an upper bound of (size of alphabet) * (size of string) comparisons.

Since the code got fairly obfuscated in the course of golfing, here is an earlier (293 byte) solution that's a bit easier to read:

e=lambda a:a&gt;i&lt;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&lt;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!'


The e function tests equivalence of characters. The exec statement assigns indices and does some variable initialisations. The first loop processes X for fall back values, and the second loop does the string search.

Update: Here is a version that exits cleanly, at the cost of one 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&lt;=M+x:
 if S[k]&gt;j&lt;W[j]or S[k]==W[j]:
    k+=1;j+=1;T+=[j]
    if j-L&gt;x:r=k=s[k-j:k]
 else:j=T[j]
'''*2%('-1;T=[0];W=S;L=M',0)
print r