BOJ 1786 찾기

1 개요

BOJ 1786 찾기

• 백준 온라인 저지 1786번 문제
• BOJ 41단계

2 C++

#include <bits/stdc++.h>
using namespace std;
 
#define INF 1e9
string T, P;
vector<int> table;
vector<int> idxs;
int cnt = 0;

void kmp() {
    int j = 0;
    for(int i=0; i < T.size(); i++) {
        while(j > 0 && T[i] != P[j]) {
            j = table[j-1];
        }
        if(T[i] == P[j]) {
            if(j == P.size()-1) {
                idxs.push_back(i - P.size() + 2);
                cnt++;
                j = table[j];
            } else {
                j++;
            }
        }
    }
}
 
void solve() {
    table.resize(P.size(), 0);
    int j = 0;
    for(int i=1; i<P.size(); i++) {
        while(j > 0 && P[i] != P[j]) {
            j = table[j-1];
        }
        if(P[i] == P[j]) {
            table[i] = ++j;
        }
    }
    kmp();
    cout << cnt << '\n';
    for(const auto& idx : idxs) {
        cout << idx << ' ';
    }
}
 
int main() {
    getline(cin, T);
    getline(cin, P);
    solve();
}