풀이 입력으로 주어진 문자열 S 안에 2N + 1길이의 Pn이 겹침을 허용해서 몇 개 존재하는지 찾으면 되는 문제다. 최대 길이 M에 대한 Pn의 길이는 (100만 - 1) 이기 때문에, 아래처럼 모든 구간에서의 Pn을 구하면 시간초과가 발생한다. N = 2, M = 15, S = IOIOIOIOIOIOIOI 일 때, IOIOI IOIOI IOIOI ... 처럼 매번 2N + 1 길이만큼의 문자열이 주어진 문제의 조건을 만족시키는지 확인하면 시간초과가 발생할 것이다. 때문에, 이미 조건을 만족시키는 문자열을 다시 확인하지 않고 풀이하는 방법이 필요하다. 먼저, 올바른 Pn이 만들어지는 조건을 살펴보자 Pn은 'I' 부터 시작한다. 문자열 S의 M - 1 번째가 'I' 아니면, Pn은 만들어지지 않는다. ..