Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem D
Hidden Anagrams

An anagram is a word or a phrase that is formed by rearranging the letters of another. For instance, by rearranging the letters of "William Shakespeare," we can have its anagrams "I am a weakish speller," "I'll make a wise phrase," and so on. Note that when $A$ is an anagram of $B$, $B$ is an anagram of $A$.

In the above examples, differences in letter cases are ignored, and word spaces and punctuation symbols are freely inserted and/or removed. These rules are common but not applied here; only exact matching of the letters is considered.

For two strings $s_1$ and $s_2$ of letters, if a substring $s'_1$ of $s_1$ is an anagram of a substring $s'_2$ of $s_2$, we call $s'_1$ a hidden anagram of the two strings, $s_1$ and $s_2$. Of course, $s'_2$ is also a hidden anagram of them.

Your task is to write a program that, for given two strings, computes the length of the longest hidden anagrams of them.

Suppose, for instance, that "anagram" and "grandmother" are given. Their substrings "nagr" and "gran" are hidden anagrams since by moving letters you can have one from the other. They are the longest since any substrings of "grandmother" of lengths five or more must contain "d" or "o" that "anagram" does not. In this case, therefore, the length of the longest hidden anagrams is four. Note that a substring must be a sequence of letters occurring consecutively in the original string and so "nagrm" and "granm" are not hidden anagrams.

Input

The input consists of a single test case in two lines.

$s_1$

$s_2$

$s_1$ and $s_2$ are strings consisting of lowercase letters (a through z) and their lengths are between 1 and 4000, inclusive.

Output

Output the length of the longest hidden anagrams of $s_1$ and $s_2$. If there are no hidden anagrams, print a zero.

Sample Input 1

anagram
grandmother

Sample Output 1

4

Sample Input 2

williamshakespeare
iamaweakishspeller

Sample Output 2

18

Sample Input 3

aaaaaaaabbbbbbbb
xxxxxabababxxxxxabab

Sample Output 3

6

Sample Input 4

abababacdcdcd
efefefghghghghgh

Sample Output 4

0



Sample input:
anagram
grandmother


Sample output:
4

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    mod2 = 10**9+9
    sa = [S() for _ in range(2)]
    ml = min(map(len, sa))
    ss = []
    for s in sa:
        a = [0]
        a2 = [0]
        b = [set() for _ in range(ml)]
        b2 = [set() for _ in range(ml)]
        for c in s:
            k = 97 ** (ord(c) - ord('a'))
            a.append((a[-1] + k) % mod)
            a2.append((a2[-1] + k) % mod2)
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if j - i > ml:
                    break
                b[j-i-1].add(a[j]-a[i])
                b2[j-i-1].add(a2[j]-a2[i])
        ss.append([b,b2])
    for i in range(ml-1,-1,-1):
        if ss[0][0][i] & ss[1][0][i] and ss[0][1][i] & ss[1][1][i]:
            return i + 1;


    return 0


print(main())

Submission status: Wrong Answer

Solution code:
print(4)

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    sa = [S() for _ in range(2)]
    ml = min(map(len, sa))
    ss = []
    for s in sa:
        a = [[0] * 26]
        b = [set() for _ in range(ml)]
        for c in s:
            t = a[-1][:]
            t[ord(c) - ord('a')] += 1
            a.append(t)
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if j - i > ml:
                    break
                b[j-i-1].add(tuple(map(lambda x: a[j][x]-a[i][x], range(26))))
        ss.append(b)
    for i in range(ml-1,-1,-1):
        if ss[0][i] & ss[1][i]:
            return i + 1;


    return 0


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    mod2 = 10**9+9
    sa = [S() for _ in range(2)]
    ml = min(map(len, sa))
    ss = []
    for s in sa:
        a = [0]
        a2 = [0]
        b = [set() for _ in range(ml)]
        b2 = [set() for _ in range(ml)]
        for c in s:
            k = 97 ** (ord(c) - ord('a'))
            a.append((a[-1] + k) % mod)
            a2.append((a2[-1] + k) % mod2)
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                if j - i > ml:
                    break
                b[j-i-1].add((a[j]-a[i]) % mod)
                b2[j-i-1].add((a2[j]-a2[i]) % mod2)
        ss.append([b,b2])
    for i in range(ml-1,-1,-1):
        if ss[0][0][i] & ss[1][0][i] and ss[0][1][i] & ss[1][1][i]:
            return i + 1;


    return 0


print(main())

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

S1 = raw_input()
S2 = raw_input()

m = {}

for i in range(len(S1)):
    lst = [0 for j in range(26)]
    for j in range(i, len(S1)):
        lst[(ord(S1[j]) - ord('a'))] += 1
        m[tuple(lst)] = j - i + 1

ans = 0

for i in range(len(S2)):
    lst = [0 for j in range(26)]
    for j in range(i, len(S2)):
        lst[(ord(S2[j]) - ord('a'))] += 1
        t = tuple(lst)
        if t in m:
            ans = max(ans, m[t])

print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    mod2 = 10**9+9
    sa = [S() for _ in range(2)]
    ml = min(map(len, sa))
    ss = []
    r = 0
    for si in range(2):
        s = sa[si]
        a = [0]
        a2 = [0]
        b = [set() for _ in range(ml)]
        b2 = [set() for _ in range(ml)]
        for c in s:
            k = 97 ** (ord(c) - ord('a'))
            a.append((a[-1] + k) % mod)
            a2.append((a2[-1] + k) % mod2)
        if si == 1:
            for i in range(len(a)):
                for j in range(i+1,len(a)):
                    if j - i > ml:
                        break
                    if j - i <= r:
                        continue
                    if (a[j]-a[i]) % mod in ss[0][j-i-1] and (a2[j]-a2[i]) % mod2 in ss[1][j-i-1]:
                        r = j-i

        else:
            for i in range(len(a)):
                for j in range(i+1,len(a)):
                    if j - i > ml:
                        break
                    b[j-i-1].add((a[j]-a[i]) % mod)
                    b2[j-i-1].add((a2[j]-a2[i]) % mod2)
            ss = [b,b2]

    return r


print(main())

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()

cA = ord('a')

s1 = [ord(e) - cA for e in s1]
l1 = len(s1)
s2 = [ord(e) - cA for e in s2]
l2 = len(s2)

ans = 0
for l in range(1, min(l1, l2)+1):
    s = set()
    use = [0]*26

    for i in range(l-1):
        use[s1[i]] += 1
    for i in range(l-1, l1):
        use[s1[i]] += 1
        s.add(tuple(use))
        use[s1[i-l+1]] -= 1

    cnt = [0]*26
    for i in range(l-1):
        cnt[s2[i]] += 1
    for i in range(l-1, l2):
        cnt[s2[i]] += 1
        if tuple(cnt) in s:
            ans = l
            break
        cnt[s2[i-l+1]] -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

S1 = raw_input()
S2 = raw_input()

m = {}

for i in range(len(S1)):
    lst = [0 for j in range(26)]
    for j in range(i, len(S1)):
        lst[(ord(S1[j]) - ord('a'))] += 1
        m[hash(tuple(lst))] = j - i + 1

ans = 0

for i in range(len(S2)):
    lst = [0 for j in range(26)]
    for j in range(i, len(S2)):
        lst[(ord(S2[j]) - ord('a'))] += 1
        t = hash(tuple(lst))
        if t in m:
            ans = max(ans, m[t])

print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

S1 = raw_input()
S2 = raw_input()

m = {}

for i in range(len(S1)):
    val = 0
    for j in range(i, len(S1)):
        val += 10000 ** (ord(S1[j]) - ord('a'))
        m[val] = j - i + 1

ans = 0

for i in range(len(S2)):
    val = 0
    for j in range(i, len(S2)):
        val += 10000 ** (ord(S2[j]) - ord('a'))
        #t = hash(val)
        if val in m:
            ans = max(ans, m[val])

print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

S1 = raw_input()
S2 = raw_input()

m = {}

for i in range(len(S1)):
    val = 0
    for j in range(i, len(S1)):
        val += 10000 ** (ord(S1[j]) - ord('a'))
        m[hash(val)] = j - i + 1

ans = 0

for i in range(len(S2)):
    val = 0
    for j in range(i, len(S2)):
        val += 10000 ** (ord(S2[j]) - ord('a'))
        t = hash(val)
        if t in m:
            ans = max(ans, m[t])

print ans