정수 과 문자열 가 주어진다.
당신은 알파벳 소문자로만 이루어진 길이가 정확히 인 문자열 를 만들어야 한다.
각 에 대해 가 의 부분 문자열(substring)로 한 번 등장할 때마다 점을 얻는다. 같은 가 여러 위치에서 등장하면 등장한 횟수만큼 점수를 얻는다. 또한 서로 다른 에 대해 일 수 있으며, 이 경우 두 문자열은 따로 점수에 기여한다.
얻을 수 있는 점수의 최댓값을 구하여라.
부분 문자열(substring)의 정의
문자열 가 문자열 의 부분 문자열로 등장한다는 것은, 어떤 정수 이 존재하여 , 이고
입력은 다음과 같은 형식으로 주어진다.
얻을 수 있는 점수의 최댓값을 출력한다.
를 만족한다는 뜻이다.
즉, 의 연속한 몇 개의 문자로 이루어진 문자열이 와 같으면 가 의 부분 문자열로 등장한다고 한다.
| 2 | 17 |
| 3 | 21 |
| 4 | 24 |
| 5 | 31 | 추가 제약이 없다. |
