[IT]/백준
[백준] 1786번 찾기 (KMP 알고리즘)
working_hard
2019. 9. 9. 20:14
728x90
- KMP 알고리즘에 대한 공부를 끝마치고 문제를 풀기 위해 찾아봤더니 바로 적용할 수 있는 문제가 있었다.
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m번 문자가 차례로 일치한다면, i를 출력하는 식이다.
www.acmicpc.net
- KMP 알고리즘만 알고 있다면 별로 어렵지 않게 풀 수 있었다.
- 처음 풀때 시간초과가 났는데 endl --> "\n" 을 해주어야 시간초과가 나지 않는다..
#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
using namespace std;
vector<int> answer;
int countt;
vector<int> makeTable(string pattern) {
int patternSize = pattern.length();
vector<int> table(patternSize, 0);
int j = 0;
for (int i = 1; i < patternSize; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = table[j - 1];
}
if (pattern[i] == pattern[j]) {
table[i] = ++j;
}
}
return table;
}
void KMP(string parent, string pattern) {
vector<int> table = makeTable(pattern);
int parentSize = parent.size();
int patternSize = pattern.size();
int j = 0;
for (int i = 0; i < parentSize; i++) {
while (j > 0 && parent[i] != pattern[j]) {
j = table[j - 1];
}
if (parent[i] == pattern[j]) {
if (j == patternSize - 1) {
countt++;
answer.push_back(i - patternSize + 2);
//printf_s("%d", i - patternSize + 2);
j = table[j];
}
else {
j++;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string parent, pattern;
countt = 0;
getline(cin, parent);
getline(cin, pattern);
KMP(parent, pattern);
cout << countt << "\n";
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << "\n";
}
return 0;
}