Submission #123005

#	Time	Username	Problem	Language	Result	Execution time	Memory
123005		model_code	Necklace (Subtask 1-3) (BOI19_necklace1)	Cpython 3	0 / 85	1573 ms	3980 KiB

necklace

def z_alg(s):
    n = len(s);
    z = [0 for i in range(n)]
    L,R = 0,0
    for i in range(1,n):
        if(i > R):
            L = R = i;
            while(R < n and s[R - L] == s[R]):
                R += 1
            z[i] = R - L
            R -= 1
        else:
            k = i - L;
            if(z[k] < R - i + 1):
                z[i] = z[k];
            else:
                L = i;
                while(R < n and s[R - L] == s[R]):
                    R += 1
                z[i] = R - L;
                R -= 1
    z[0] = n
    return z;
s = input()
t = input()
n,m = len(s),len(t)
ans,ind1,ind2 = 0,0,0
for times in range(2):
    for k in range(m+1):
        ls,rs = t[k:],t[:k]
        l = z_alg(ls+s)[len(ls):]
        r = z_alg((s+rs)[::-1])[len(rs):][::-1]
        for i in range(n):
            l[i] = min(l[i],len(ls))
            r[i] = min(r[i],len(rs))
        ZERO = 3002
        best_l = [int(-1e4) for i in range(2*ZERO)]
        best_r = [int(-1e4) for i in range(2*ZERO)]
        for i in range(0,n):
            best_l[l[i]+i] = max(best_l[l[i]+i],1-i)
            best_r[r[i]-i-1+ZERO] = max(best_r[r[i]-i-1+ZERO],i)
        for i in range(2*ZERO-2,-1,-1):
            best_l[i] = max(best_l[i],best_l[i+1])
            best_r[i] = max(best_r[i],best_r[i+1])
        for x in range(0,2*ZERO):
            y = max(-x+ZERO,0)
            if ans < best_l[x] + best_r[y]:
                ans = best_l[x] + best_r[y]
                ind1 = -(best_l[x]-1)
                ind2 = k-r[best_r[y]]
                if times:
                    ind2 = m-ind2-ans




    t = t[::-1]
print(ans)
print(ind1,ind2)

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40