ㅋㅋ루ㅋㅋ
시간 제한1초메모리 제한1024 MB
K와 R로 이루어진 문자열이 주어질 때, K...K R...R K...K 형태(비어 있지 않은 R 블록 양쪽을 K가 감싸는 형태)의 가장 긴 부분수열의 길이를 구한다.
문제
ㅋㅋ루ㅋㅋ 문자열은 다음과 같이 정의한다.
R로만 이루어진 문자열은 ㅋㅋ루ㅋㅋ 문자열이다. 단, 빈 문자열은 ㅋㅋ루ㅋㅋ 문자열이 아니다.- ㅋㅋ루ㅋㅋ 문자열 양 끝에
K를 하나씩 붙인 문자열은 ㅋㅋ루ㅋㅋ 문자열이다.
입력
첫째 줄에 K와 R로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 3,000,000이다.
출력
주어진 문자열의 부분 수열 중 가장 긴 ㅋㅋ루ㅋㅋ 문자열의 길이를 출력한다. 부분 수열 중 ㅋㅋ루ㅋㅋ인 문자열이 없는 경우, 0을 출력한다.
힌트
어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다.