提出 #684198

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = input()
s = raw_input()
# SA-IS (O(nlogn))
def SuffixArray(s):
    m = map(ord, s)
    m.append(-1)
    n = len(m)
    def i_large(t, SA, s, bktl):
        bkt = {}
        for k in bktl: bkt[k] = bktl[k]
        for e in SA:
            j = e-1
            if j>=0 and not t[j]:
                SA[bkt[s[j]]] = j
                bkt[s[j]] += 1
    def i_small(t, SA, s, bkts):
        bkt = {}
        for k in bkts: bkt[k] = bkts[k]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n = input()
s = raw_input()

# SA-IS (O(nlogn))
def SuffixArray(s):
    m = map(ord, s)
    m.append(-1)
    n = len(m)

    def i_large(t, SA, s, bktl):
        bkt = {}
        for k in bktl: bkt[k] = bktl[k]
        for e in SA:
            j = e-1
            if j>=0 and not t[j]:
                SA[bkt[s[j]]] = j
                bkt[s[j]] += 1

    def i_small(t, SA, s, bkts):
        bkt = {}
        for k in bkts: bkt[k] = bkts[k]
        for e in reversed(SA):
            j = e-1
            if j>=0 and t[j]:
                bkt[s[j]] -= 1
                SA[bkt[s[j]]] = j

    def SAIS(s, n):
        t = [0]*n; LMS = [0]*n
        SA = [0]*n

        t[-2] = 0; t[-1] = 1
        for i in xrange(n-3, -1, -1):
            t[i] = 1 if s[i]<s[i+1] or (s[i]==s[i+1] and t[i+1]) else 0
        for i in xrange(1, n):
            LMS[i] = 1 if t[i] and not t[i-1] else 0

        su = 0
        bkt = {}
        bktl = {}; bkts = {}
        for c in s: bkt[c] = bkt.get(c, 0) + 1
        for k in sorted(bkt):
            bktl[k] = su
            su += bkt[k]
            bkts[k] = su

        for k in bkts: bkt[k] = bkts[k]
        for i in xrange(n): SA[i] = -1
        for i in xrange(1, n):
            if LMS[i]:
                bkt[s[i]] -= 1
                SA[bkt[s[i]]] = i

        i_large(t, SA, s, bktl)
        i_small(t, SA, s, bkts)

        n1 = 0
        for e in SA:
            if e>0 and LMS[e]:
                SA[n1] = e
                n1 += 1

        for i in xrange(n1, n): SA[i] = -1
        cnt = 0; prev = -1
        for i in xrange(n1):
            pos = SA[i]
            for d in xrange(n):
                if prev==-1 or s[pos+d]!=s[prev+d] or t[pos+d]!=t[prev+d]:
                    cnt += 1
                    prev = pos
                    break
                elif LMS[pos+d] or LMS[prev+d]: break
            pos /= 2
            SA[n1+pos] = cnt-1
        j = n-1
        for i in xrange(n-1, n1-1, -1):
            if SA[i]>=0:
                SA[j] = SA[i]
                j -= 1

        if cnt<n1:
            SA[:n1] = SAIS(SA[-n1:], n1)
        else:
            for i in xrange(n1): SA[SA[i-n1]] = i

        for k in bkts: bkt[k] = bkts[k]
        j = 0
        for i in xrange(1, n):
            if LMS[i]:
                SA[j-n1] = i
                j += 1
        for i in xrange(n1): SA[i] = SA[SA[i]-n1]
        for i in xrange(n1, n): SA[i] = -1

        for i in xrange(n1-1, -1, -1):
            j = SA[i]; SA[i] = -1
            bkt[s[j]] -= 1
            SA[bkt[s[j]]] = j

        i_large(t, SA, s, bktl)
        i_small(t, SA, s, bkts)
        return SA
    return SAIS(m, n)

rank = [0]*(n+1)
def LCP(s, n, sa):
    lcp = [-1]*(n+1)
    #rank = [0]*(n+1)
    for i in xrange(n+1): rank[sa[i]] = i

    h = 0
    lcp[0] = 0
    for i in xrange(n):
        j = sa[rank[i] - 1]
        if h > 0: h -= 1
        while j+h < n and i+h < n and s[j+h]==s[i+h]:
            h += 1
        lcp[rank[i] - 1] = h
    return lcp

sa = SuffixArray(s)
lcp = LCP(s, n, sa)

# LCP StarrySkyTree
class LCPSST:
    def __init__(self, sa, lcp):
        n0 = len(lcp)
        n = 1
        while n < n0:
            n *= 2
        self.n = n
        self.data = data = [10**9]*(2*n)
        self.sa = sa
        for i in xrange(n0):
            data[i+n-1] = lcp[i]
        for i in xrange(n-2, -1, -1):
            data[i] = min(data[2*i+1], data[2*i+2])
    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 10**9
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self.__query(a, b, 2*k+1, l, (l + r) / 2)
            vr = self.__query(a, b, 2*k+2, (l + r) / 2, r)
            return min(vl, vr)
    def __call__(self, i, j):
        sa = self.sa
        a = rank[i]; b = rank[j]
        #print rank[i], rank[j]
        if a > b:
            a,b = b,a
        return self.__query(a, b, 0, 0, self.n)

lcpq = LCPSST(sa, lcp)

# i < j
# XXXXXX YYY
# YYY XXXXXX
def comp(i, j):
    res = 1
    if i > j:
        i,j = j,i
        res = -1
    r = lcpq(i, j)
    #print i, j, r, n-(j-i)
    if r < n-j:
        return cmp(rank[i], rank[j])*res
    r = lcpq(n+i-j+1, i)
    #print n+i-j+1, i, r
    if r < j-i:
        return cmp(rank[n+i-j+1], rank[i])*res
    return 0

a = range(0, n)
a.sort(cmp=comp)

print "\n".join(map(str, map(lambda x: x+1, a)))

提出情報

ジャッジ結果