https://www.acmicpc.net/problem/5836


solved.ac에서 KMP로 분류되어 있길래 풀어보려다가 도저히 모르겠어서 포기했습니다.


http://www.usaco.org/current/data/sol_necklace.html


정해는 DP인데 풀이를 읽어봐도 어떻게 동작하는 것인지 전혀 모르겠어서 질문 올립니다.


제가 이해한 부분은 이것 밖에 없습니다.


첫 번째 문자열을 S, 두 번째 문자열을 T라고 하면

이 문제는 T가 등장하지 않는 S의 부분 수열의 최대 길이를 구하는 문제이다.

N - (최대 길이) 를 출력하면 된다.


예시 코드에서는 next 배열과 next_taken 배열을 사용하는데 여기에 들어가는 값이 정확히 무엇을 의미하는지 모르겠습니다.


next 배열과 next_taken 배열의 의미를 알려주신다면 큰 도움이 될 것 같습니다.


답변 주시면 감사하겠습니다.