문제 설명
나무를 숨기려면 숲에 숨기고, 사람을 숨기려면 인파 속에 숨기라는 말이 있습니다.
오히려 가장 흔한 곳에 가장 눈에 띄는 곳에 숨겨야 덜 티가 난다는 뜻입니다.
이는 나무, 사람 뿐만 아니라 다른 사물 등에도 동일하게 적용됩니다.
이 사실을 잘 알고 있는 문자열 X는 친구들과 숨바꼭질 놀이를 할 때, 긴 문자열 속으로 숨어버릴 계획을 세웠습니다.
놀이는 시작했고, 술래 문자열이 잠시 기다리는 사이 문자열 X는 적당히 긴 문자열 속에 들어가 숨었습니다.
술래 문자열은 다른 모든 문자열을 금방 찾았지만 문자열 X만을 못 찾고 있었습니다.
그러던 중 의심이 가는 긴 문자열 Y을 발견했지만, 너무 길어서 자신이 직접 찾다가는 날이 꼬박 새버릴 것을 알고 있습니다.
술래 문자열을 위해 긴 문자열 Y와 문자열 X가 주어지면 Y에서 X가 등장하는 모든 시작 위치를 찾아주는 프로그램을 작성해주세요.
입력 설명
첫 줄에 전체 테스트 케이스 T (1<= T <= 10)가 주어지며, 그 다음 줄부터는 다음의 규칙으로 입력이 주어진다.
각 테스트 케이스에는 문자열 Y와 문자열 X가 공백으로 구분되어 주어진다.
문자열은 알파벳 소문자(a-z)로만 구성되어 있으며, 1 <= |X| <= |Y| <= 300,000을 만족한다(|S| = 문자열 S의 길이).
출력 설명
각 테스트 케이스마다 첫 줄에 문자열 T에서 문자열 P가 등장하는 횟수를, 둘째 줄에 등장하는 시작 위치를 공백으로 구분하여 출력한다.
만약 한 번도 등장하지 않으면 첫 줄에 0을 출력한다.
3
banana ana
qwerty asdf
aaaaa aaa
도움
이 문제는 라이브러리에 있는 부분 문자열 매칭 함수를 사용하여 해결할 수 없습니다.