문자열 매칭 (Small)
텍스트 문자열 \(T\)와 패턴 문자열 \(P\)가 주어졌을 때, \(T\) 안에서 \(P\)가 몇 번 나타나는지 구하고, \(P\)가 나타나는 모든 시작 위치를 찾는 프로그램을 작성하시오.
문자열의 위치는 \(1\)부터 센다. 서로 겹치는 구간에서 \(P\)가 나타나는 경우에도 각각 하나의 매칭으로 센다.
예를 들어, \(T=\text{CATGCATGATCATGCATGAT}\)이고 \(P=\text{CATGAT}\)이라면, \(P\)는 \(T\)의 5번째 문자와 15번째 문자에서 각각 시작한다. 따라서 매칭 횟수는 \(2\)이고 시작 위치는 \(5,15\)이다.
입력
첫째 줄에 텍스트 문자열 \(T\)가 주어진다.
둘째 줄에 패턴 문자열 \(P\)가 주어진다.
\(T\)와 \(P\)는 알파벳 대소문자로만 이루어져 있으며 공백은 포함되지 않는다. 알파벳의 대문자와 소문자는 서로 다른 문자로 취급한다.
출력
첫째 줄에 \(T\)에서 \(P\)가 나타나는 횟수를 출력한다.
둘째 줄에 각 매칭의 시작 위치를 오름차순으로 공백으로 구분하여 출력한다. 매칭되는 위치가 없으면 둘째 줄에 빈 줄을 출력한다.
제한 사항
- \(1 \le |P| \le |T| \le 1,000\)
- \(|P| \le 20\)
예제 입력 1
CATGCATGATCATGCATGAT
CATGAT
예제 출력 1
2
5 15
예제 입력 2
AAAA
AA
예제 출력 2
3
1 2 3
예제 설명 2
패턴 AA는 1번째, 2번째, 3번째 문자에서 시작한다. 서로 겹치는 매칭도 모두 세므로 총 \(3\)번 나타난다.
코멘트
define _CRT_SECURE_NO_WARNINGS
include<stdio.h>
include<stdlib.h>
include<iostream>
include<algorithm>
include<stack>
include<queue>
include<vector>
include<string.h>
include<math.h>
using namespace std;
char t[1009]; char p[1009]; queue<int>q;
int main() { scanf("%s", t); scanf("%s", p); for (int i = 0; i < strlen(t) - strlen(p) + 1; i++) { int chk = 0; for (int j = 0; j < strlen(p); j++) { if (t[i + j] != p[j]) { chk = 1; break; } } if (!chk) { q.push(i + 1); } } printf("%d\n", q.size()); while (q.size()) { printf("%d ", q.front()); q.pop(); } }