문자열 찾기
플래티넘 V의견: 0
문자열 \(S\) (본문)와 문자열 \(P\) (패턴)가 주어진다. 패턴 \(P\) 가 본문 \(S\) 안에 몇 번 나타나는지, 그리고 나타나는 모든 위치를 구하여라.
여기서 "위치"란 \(P\) 가 시작하는 \(S\) 의 인덱스(맨 앞 글자가 \(1\))를 뜻한다. 서로 겹치는 출현도 각각 따로 센다. 예를 들어 \(S = \) aaaaa, \(P = \) aa 이면 \(P\) 는 위치 \(1, 2, 3, 4\) 에서 시작하여 총 \(4\) 번 나타난다.
\(1 \le |P| \le |S| \le 2 \cdot 10^5\) 인 경우가 대부분이지만, \(|P| > |S|\) 일 수도 있다 (이때 답은 \(0\)).
\(1 \le |S|, |P| \le 2 \cdot 10^5\)
첫째 줄에 본문 문자열 \(S\) 가 주어진다.
둘째 줄에 패턴 문자열 \(P\) 가 주어진다.
두 문자열은 알파벳 소문자와 대문자로만 이루어진다.
첫째 줄에 \(P\) 가 \(S\) 안에 나타나는 횟수를 출력한다.
둘째 줄에 \(P\) 가 시작하는 위치들을 오름차순으로 공백으로 구분하여 출력한다. 한 번도 나타나지 않으면 첫째 줄에 \(0\) 을 출력하고 둘째 줄은 비워 둔다.
ABABABCABABABCABAB
ABABAB
2
1 8
패턴 ABABAB 은 본문에서 \(1\), \(8\) 번째 위치에서 시작하여 나타나므로 출현 횟수는 \(2\) 이다. (겹치는 출현도 모두 센다.)
aaaaa
aa
4
1 2 3 4
aa 는 위치 \(1, 2, 3, 4\) 에서 겹쳐 가며 \(4\) 번 나타난다.
abcdef
xyz
0
패턴이 본문에 한 번도 나타나지 않으므로 첫 줄에 \(0\) 을 출력하고 둘째 줄은 비운다.
riseoj 작성
출처 Original
평가 및 의견
문자열 찾기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
문자열 찾기