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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
3980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
3980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
3980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
