cho.sh

유사 팰린드롬

문자열 w와 유리수 theta가 주어질 때, 각 조각이 theta-팰린드롬(uvu^R 꼴이며 경계가 충분히 긴 문자열)이 되도록 w를 최소 개수로 나누고, 불가능하면 0을 출력한다.

어려움8동적 계획법문자열 매칭해시맵아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

영선이는 팰린드롬을 좋아해서 이상형도 팰린드롬을 좋아하는 사람이다. 그런데 기준이 너무 까다로워 이상형을 찾지 못했다. 그래서 영선이는 기준을 낮춰, 완벽한 팰린드롬 대신 유사 팰린드롬을 좋아하는 사람도 이상형으로 받아들이기로 했다.

실수 θ\theta (0<θ≤10 < \theta \le 1)에 대해 문자열 ww가 다음 조건을 모두 만족하면 ww를 θ\theta-팰린드롬이라고 한다.

  1. ww를 w=uvuRw = u v u^R 꼴로 나눌 수 있다. uRu^R은 uu를 뒤집은 문자열이다. 예를 들어 u=abu = \texttt{ab}이면 uR=bau^R = \texttt{ba}이다.
  2. vv는 빈 문자열이어도 되지만 uu는 빈 문자열일 수 없다.
  3. θ≤2∣u∣/∣w∣\theta \le 2|u|/|w|가 성립한다. 여기서 ∣s∣|s|는 문자열 ss의 길이다.

예를 들어 θ=0.8\theta = 0.8이고 w=ababaw = \texttt{ababa}라면 u=abu = \texttt{ab}, v=av = \texttt{a}로 잡아 0.8≤2⋅2/50.8 \le 2 \cdot 2 / 5가 성립하므로 ww는 θ\theta-팰린드롬이다.

영선이가 길에서 들은 문자열은 하나도 θ\theta-팰린드롬이 아니었다. 영선이는 기준을 한 번 더 낮춰, θ\theta-팰린드롬 몇 개를 순서대로 이어 붙여 만들 수 있는 문자열도 좋아하기로 했다. 대신 이어 붙인 θ\theta-팰린드롬의 개수가 적을수록 더 좋아한다.

예를 들어 θ=0.5\theta = 0.5이고 w=abbaabaw = \texttt{abbaaba}라면 u=abu = \texttt{ab}, v=baav = \texttt{baa}로 잡아 0.5≤4/70.5 \le 4/7이므로 ww 자체가 θ\theta-팰린드롬이다. 반면 θ=0.6\theta = 0.6이면 ww 자체는 θ\theta-팰린드롬이 아니지만, θ\theta-팰린드롬인 abba\texttt{abba}와 aba\texttt{aba}를 이어 붙이면 abbaaba\texttt{abbaaba}가 된다.

문자열 ww와 θ\theta가 주어질 때, ww를 만드는 데 필요한 θ\theta-팰린드롬 개수의 최솟값을 구하는 프로그램을 작성하시오. 조각 하나를 판정할 때 조건 3의 ∣w∣|w|는 그 조각 자체의 길이를 뜻한다.

입력

첫째 줄에 세 정수 nn, kk, ll이 공백으로 구분되어 주어진다 (1≤n≤100001 \le n \le 10000, 1≤k≤l≤1001 \le k \le l \le 100). nn은 문자열 ww의 길이이고, θ=k/l\theta = k / l이다.

둘째 줄에 알파벳 소문자로 이루어진 문자열 ww가 주어진다.

출력

ww를 만드는 데 필요한 θ\theta-팰린드롬 개수의 최솟값을 출력한다. θ\theta-팰린드롬을 이어 붙여 ww를 만들 수 없으면 0을 출력한다.