8071 : 패턴 매칭
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
텍스트 문자열 $T$와 패턴 문자열 $P$가 주어집니다.
텍스트 $T$ 내부에서 패턴 $P$가 출현하는 모든 시작 위치(1-indexed)를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le |T| \le 100{,}000$
• $1 \le |P| \le 100{,}000$
• 각 문자열은 알파벳 소문자로만 구성됩니다.
텍스트 $T$ 내부에서 패턴 $P$가 출현하는 모든 시작 위치(1-indexed)를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le |T| \le 100{,}000$
• $1 \le |P| \le 100{,}000$
• 각 문자열은 알파벳 소문자로만 구성됩니다.
입력 설명
첫째 줄에 텍스트 문자열 $T$가 주어집니다. ($1 \le |T| \le 100{,}000$)
둘째 줄에 패턴 문자열 $P$가 주어집니다. ($1 \le |P| \le 100{,}000$)
각 문자열은 알파벳 소문자로만 구성됩니다.
둘째 줄에 패턴 문자열 $P$가 주어집니다. ($1 \le |P| \le 100{,}000$)
각 문자열은 알파벳 소문자로만 구성됩니다.
출력 설명
첫째 줄에 패턴 $P$가 텍스트 $T$ 안에서 매칭되는 총 횟수 $K$를 출력합니다.
둘째 줄에 매칭이 시작되는 문자열 $T$ 내의 시작 위치 인덱스(1-indexed)들을 공백으로 구분하여 오름차순으로 출력합니다.
출현 횟수가 0인 경우, 둘째 줄은 빈 줄을 출력합니다.
둘째 줄에 매칭이 시작되는 문자열 $T$ 내의 시작 위치 인덱스(1-indexed)들을 공백으로 구분하여 오름차순으로 출력합니다.
출현 횟수가 0인 경우, 둘째 줄은 빈 줄을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
aybabtuaybabtu
aybabtu
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1 8도움
KMP 알고리즘의 실패 함수(Failure Function)를 활용하여 $O(|T| + |P|)$의 시간 복잡도 내에 패턴 매칭을 찾아냅니다.
또는 Z-알고리즘을 통해 $O(|T|)$에 구하는 것도 가능합니다.
또는 Z-알고리즘을 통해 $O(|T|)$에 구하는 것도 가능합니다.