길이 101의 매칭을 찾아야 한다고 가정해 봅시다. 그런데 1~101번째 문자가 매칭된다면, 굳이 3~103번째 문자도 매칭되는지 알기 위해 3~101번째 문자들을 다시 확인해보아야 할 필요가 있을까요?
비슷하게 만일 1~100번째 문자는 매칭되는데 101번째 문자가 매칭되지 않는다면, 이후 3~103번째 문자가 매칭되는지를 확인해 볼 필요가 있을까요?
또한 만일 1번째부터 1001번째 문자까지가 모두 IOIOI...IOI의 패턴을 가지는 것을 확인할 수 있다면, 이 안에서 1~101, 3~103, 5~105, ...을 모두 개별적으로 확인해 볼 필요가 있을까요? 그 안에 길이 101의 매칭은 총 몇 개가 있을까요?
이런 관찰들을 종합해서 효율적인 풀이를 구상해 보시면 좋을 것 같습니다.
별개로 서브태스크별 채점 결과는 코드를 열면 하단에서 확인할 수 있습니다.

rmm1 1년 전
계속 50점이 나오는데 아마 시간 초과인 것 같아서요
처음에는 IOI...IOI 문자열을 찾아서 이 길이 기반으로 PN이 들어가는 개수를 계산하는 방식으로 하다가 인덱스 제어가 까다로워서 단순하게 바꿨는데 처음으로 돌아가야 할까요?
KMP나 라빈 카프 없이도 풀 수 있을 것 같은데, 다른 아이디어가 있을까요?