Submission #48761

#	Time	Username	Problem	Language	Result	Execution time	Memory
48761		leejseo	구간 성분 (KOI15_interval)	Pypy 2	30 / 100	686 ms	131072 KiB

interval

from bisect import bisect_left as bl
from bisect import bisect_right as br
A = raw_input()
B = raw_input()
N = len(A)
M = len(B)
va = [ ord(i) - 96 for i in A ]
vb = [ ord(i) - 96 for i in B ]
hchar = [98213451]
for i in xrange(1, 27):
    hchar.append((hchar[-1] * hchar[0])%1000000009)
A = None
B = None
sa = [0]*(N+1)
sb = [0]*(M+1)
cha = [ [0]*(N+1) for i in xrange(27) ]
chb = [ [0]*(M+1) for i in xrange(27) ]
for i in xrange(N):
    sa[i+1] = sa[i] + hchar[va[i]]
    for c in xrange(1, 27): cha[c][i+1] = cha[c][i]
    cha[va[i]][i+1] += 1
for i in xrange(M):
    sb[i+1] = sb[i] + hchar[vb[i]]
    for c in xrange(1, 27): chb[c][i+1] = chb[c][i]
    chb[vb[i]][i+1] = chb[vb[i]][i] + 1
inb   = []
inb_v = []
for k in xrange(M):
    for i in xrange(M-k):
        inb.append((sb[i+k+1] - sb[i], k, i))
        inb_v.append(sb[i+k+1] - sb[i])
inb.sort();inb_v.sort()
ans = 0
for k in xrange(N):
    for i in xrange(N-k):
        if k+1 == ans : break
        val = sa[i+k+1] - sa[i]
        st, ed = bl(inb_v, val), br(inb_v, val)
        for j in xrange(st, ed):
            if k+1 == ans: break
            nv, nk, ni = inb[j]
            if k != nk: continue
            b = True
            for c in xrange(1, 27):
                if cha[c][i+k+1] - cha[c][i] != chb[c][ni+nk+1] - chb[c][ni] : b = False; break
            if b : ans = max(ans, k+1)
print ans

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 31
• Subtask 4: 0 / 39