BOJ/백준 1786번 찾기

 

문제 - https://www.acmicpc.net/problem/1786 

1786번: 찾기

문제자체는 KMP 알고리즘을 사용해서 푸는 문제이다 

KMP 알고리즘에 대한 설명은 동빈나님 블로그에서 보는게 좋을꺼 같다 영상이 있어서 이해하기 편했다

동빈나님 블로그 - https://blog.naver.com/ndb796/221240660061

 

참고로 문제를 입력받을때 문자열이랑 패턴 둘다 띄워쓰기로 입력받아야한다
난 문자열만 공백입력을 받는줄알고 하루종일 맞왜틀을 외쳤다

 

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 백준 1786번
vector<int> makeTable(string word) {
    int word_size = word.size();
    vector<int> table(word_size, 0);
    int j = 0; // j는 word의 커서임 j는 접두사의 커서 i는 접미사의 커서
    for (int i = 1; i < word_size; i++) { //  i는 1부터 시작 접두 접미사 부분이 일치하는지 확인 
        while (j > 0 && word[i] != word[j]) { // i 인덱스의 값이랑 j 인덱스의 값이 일치하지 않으면
            j = table[j - 1]; //  j - 1의 인덱스의 값을 j에 넣음.
        }
        if (word[i] == word[j]) { // i 인덱스랑 j 인덱스의 값이 일치하다면
            table[i] = ++j; // table의 i위치에 현재 j 값의 + 1을 해서 넣음 
        }
    }
    return table; /
}
 
vector<int> KMP(string str, string word) {
    vector<int> solve;
    auto table = makeTable(word);
    int str_size = str.size();
    int word_size = word.size();
    int j = 0;
    for (int i = 0; i < str_size; i++) {
        while (j > 0 && str[i] != word[j]) {
            j = table[j - 1];
        }
        if (str[i] == word[j]) {
            if (j == word_size - 1) {
                solve.push_back(i - word_size + 2); // 현재 i에서 찾는단어의 길이 만큼 빼고 + 2를 해줌 찾은 위치를 문자로 보면 +2, 인덱스로 보면 +1
                j = table[j];
            }
            else {
                j++;
            }
        }
    }
    return solve;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str, word;
    getline(cin, str);
    getline(cin, word);
    auto solve = KMP(str, word);
    cout << solve.size() << '\n';
    int size = solve.size();
    for (int i = 0; i < size; i++) {
        cout << solve[i] << '\n';
    }
    return 0;
}

결과

앞으로는 문제를 잘 읽어 봐야겠다.