물음표가 섞인 패턴 찾기
다이아몬드 IV의견: 0
텍스트 \(T\)와 패턴 \(P\)가 주어진다. 두 문자열 모두 소문자 알파벳과 와일드카드 문자 ?로 이루어져 있다. 와일드카드 ?는 임의의 한 글자(다른 ?도 포함)와 일치한다고 본다.
패턴 \(P\)가 텍스트 \(T\)의 어느 위치에서 일치하는지 모두 찾아라. 즉, \(P\)를 \(T\)의 위치 \(i\)에 겹쳐 놓았을 때 모든 칸에서 (한쪽이 ?이거나 두 글자가 같아) 일치하는 시작 위치 \(i\)를 모두 구한다.
\(|T|\)와 \(|P|\)가 커서 단순 비교 \(O(|T| \cdot |P|)\)는 통과할 수 없다.
\(1 \le |P| \le |T| \le 200{,}000\)
\(T\), \(P\)는 소문자 알파벳과 ?로만 이루어진다.
첫 줄에 텍스트 \(T\), 둘째 줄에 패턴 \(P\)가 주어진다.
첫 줄에 일치하는 위치의 개수 \(c\)를 출력한다. 둘째 줄에 일치가 시작되는 위치들을 오름차순으로 공백으로 구분해 출력한다(위치는 \(1\)부터 시작). \(c=0\)이면 둘째 줄은 비워 둔다.
abcabc
a?c
2
1 4패턴 a?c는 가운데가 임의 글자. T=abcabc에서 위치 1(abc)과 위치 4(abc)에서 일치한다.
aaaa
?b
0
패턴 ?b는 둘째 글자가 반드시 b여야 한다. T=aaaa에는 b가 없으므로 일치하는 위치가 없다.
riseoj 작성
출처 Original
평가 및 의견
물음표가 섞인 패턴 찾기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
물음표가 섞인 패턴 찾기