만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

팰린드롬 배열

시간 제한2초메모리 제한512 MB

요약
두 배열에서 같은 길이의 연속 구간을 골라 원소별 합이 회문이 되도록 할 때, 가능한 가장 긴 길이를 구합니다.
난이도

보통10점 중 7점

유형
배열, 문자열 매칭
정답자
아직 제출이 없습니다

문제

카이는 배열 실험실에서 자연수로 이루어진 두 배열을 가지고 실험한다. 길이가 nn인 배열 A=[a1,a2,…,an]A = [a_1, a_2, \ldots, a_n]과 길이가 mm인 배열 B=[b1,b2,…,bm]B = [b_1, b_2, \ldots, b_m]이다. 실험은 다음과 같이 진행된다. 각 배열에서 임의의 접두사와 임의의 접미사를 잘라낸다. 둘 다 비어 있어도 된다. 남은 두 부분의 길이는 같아야 한다. 남은 배열을 A′A', B′B'라 하고, 공통 길이를 kk라 한다. 그런 다음 카이는 두 배열을 원소별로 더해 배열 C=[c1,c2,…,ck]C = [c_1, c_2, \ldots, c_k]를 만든다. 예를 들어 n=5n = 5, A=[4,3,3,2,1]A = [4, 3, 3, 2, 1], m=6m = 6, B=[4,1,5,1,3,2]B = [4, 1, 5, 1, 3, 2]라고 하자. 카이는 AA에서 첫 원소와 마지막 원소를 버리고, BB에서 처음 세 원소를 버린다. 그러면 A′=[3,3,2]A' = [3, 3, 2], B′=[1,3,2]B' = [1, 3, 2]이고, 원소별 합은 C=[4,6,4]C = [4, 6, 4]이다. 카이는 CC가 팰린드롬 배열이기를 원한다. 즉 모든 ii에 대해 위치 ii와 위치 k−i+1k - i + 1의 원소가 같아야 한다. 카이가 실험으로 얻을 수 있는 팰린드롬 배열의 최대 길이를 구하라.

입력

첫 줄에 두 정수 nn과 mm이 주어진다. 각각 첫 번째 배열과 두 번째 배열의 원소 개수다 (1≤n,m≤1000001 \leq n, m \leq 100000). 둘째 줄에는 배열 AA의 정수 nn개 aia_i가 주어진다 (1≤ai≤1001 \leq a_i \leq 100). 셋째 줄에는 배열 BB의 정수 mm개 bjb_j가 주어진다 (1≤bj≤1001 \leq b_j \leq 100).

출력

카이가 실험으로 길이 kk의 팰린드롬 배열을 얻을 수 있는 최대 kk를 정수 하나로 출력하라.

예제1

  1. 예제 1

    입력
    5 6
    4 3 3 2 1
    4 1 5 1 3 2
    
    예상 출력
    3