목록dp + 아호코라식 (1)
블로그 옮겼습니다
Topcoder SRM 519 Div1(Medium) RequiredSubstrings
https://community.topcoder.com/stat?c=problem_statement&pm=11514 \(1\leq{N}\leq{50}\)\(1\leq{C}\leq{N}\)\(1\leq{L}\leq{50}\)문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..
Algorithm/Problem Solving
2017. 5. 3. 21:40