kjk9704   1년 전

[문제]

대문자 알파벳으로만 구성하는 길이 N인 문자열 S과 크기가 작은 0 이상의 정수 K가 주어집니다.

대문자 알파벳으로만 구성하는 길이 N인 문자열 T 중에서 S와 T의 LCS 길이가 N - K 이상인 T의 개수를 구하시오.

단, 정답이 클 수 있으므로 10^9 + 7로 나눈 나머지를 출력하시오.

문자열 S(s1s2...sn)이 문자열 T(t1t2...tm)의 부분 수열이라는 것은, 증가하는 지수열 1 <= i_1 < i_2 < ... < i_n <= m가 존재하여 모든 1 <= x <= n에 대해 s_x = t_(i_x)를 만족함을 뜻합니다.
[입력]

첫째 줄에 길이 N인 문자열 S가 주어집니다. 이 때 S의 길이는 1 이상 50,000 이하이고 S의 모든 문자는 대문자 알파벳입니다.

둘째 줄에 정수 K가 하나 주어집니다. 이 때 K는 0 이상 3 이하의 정수입니다.

[출력]

문제에서 주어진 T의 개수를 10^9 +으로 나눈 값을 출력하시오.

댓글을 작성하려면 로그인해야 합니다.