레이팅 미적용설명
소 베시(Bessie)는 각각 알파벳 글자 하나가 새겨진 N개의 돌을 한 줄로 늘어놓았고, 이것으로 멋진 목걸이를 만들고 싶어 한다.
소지품을 지키고 싶은 베시는, 현재 헛간의 자기 쪽에 사는 다른 소와 목걸이를 공유하고 싶지 않다. 그 소의 이름은 M개의 문자로 이루어진 문자열인데, 베시는 이 길이 M의 문자열이 자기 목걸이를 나타내는 문자열의 어디에도 연속 부분 문자열로 나타나지 않기를 바란다 (그렇지 않으면 그 소가 목걸이를 자기 것이라고 착각할 수 있다). 베시는 목걸이에서 돌 몇 개를 빼서 그 소의 이름이 부분 문자열로 나타나지 않게 하기로 했다. 베시가 빼야 하는 돌의 최소 개수를 구하는 것을 도와주자.
제약
입력 형식
첫째 줄: 베시의 처음 목걸이를 나타내는 길이 N의 문자열. 각 문자는 "a"부터 "z"까지의 범위이다.
둘째 줄: 헛간의 다른 소의 길이 M의 이름. 역시 "a"부터 "z"까지의 문자로 이루어져 있다.
테스트 케이스의 20% 이상에서 N <= 20이다. 테스트 케이스의 60% 이상에서 N <= 1000, M <= 100이다. 모든 테스트 케이스에서 N <= 10000, M <= 1000, M <= N이다.
출력 형식
베시의 목걸이에 다른 소의 이름이 부분 문자열로 포함되지 않도록 하기 위해 빼야 하는 돌의 최소 개수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
necklace.in · 출력을 쓸 파일 necklace.out예제 1
입력
ababaa
aba출력
1설명
Output details: The modified necklace should be "abbaa".
문제 정보
태그