[ 백준 ] 1786번 - 찾기 (C++)

https://www.acmicpc.net/problem/1786

1786번: 찾기

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 걸 추천드립니다!

https://rudalsd.tistory.com/69?category=1064608 

[ 알고리즘 ] KMP 알고리즘(KMP Algorithm)

 

입력되는 문자열에 공백이 포함되어 있으므로 getline(cin, string) 함수를 사용해서 값을 입력받은 후 KMP 알고리즘을 활용하여 문제를 풀면 됩니다.

 

[ 소스 코드 ]

 

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string T, P;
vector<int> Pi;
vector<int> ans;
 
void findK(string P)        //찾을 문자열 P 전처리
{
    Pi.resize(P.size());
 
    int cur = 0;
 
    for (int i = 1; i < P.size(); i++) {
        while (P[i] != P[cur] && cur > 0) {
            cur = Pi[cur - 1];
        }
        if (P[i] == P[cur]) {
            Pi[i] = cur + 1;
            cur++;
        }
    }
}
 
void KMP(string T, string P)    //T에서 P찾기
{
    int cur = 0;
    for (int i = 0; i < T.size(); i++) {
        while (cur > 0 && T[i] != P[cur]) {
            cur = Pi[cur - 1];
        }
        if (T[i] == P[cur]) {
            if (cur == P.size() - 1) {
                ans.push_back(i - cur + 1);
                cur = Pi[cur];
            }
            else {
                cur++;
            }
        }
    }
}
 
int main()
{
    getline(cin, T);
    getline(cin, P);
 
    findK(P);
 
    KMP(T, P);
 
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}