[백준] 1543번 문서 검색

[문제] 

문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 문제 입니다.

예로, 문서가 abababa가 있을때 찾으려는 문장이 ababa 라면 중복되지 않게 1번 등장합니다.

 

[풀이]

이 문제는 KMP 문자열 탐색 알고리즘을 쓰면 간단하게 해결되는 문제 입니다. 

제 블로그의 문자열 탐색 알고리즘 KMP에 코드와 함께 설명을 작성해 두었습니다 :)

 

아래는 문제 풀이한 코드입니다.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
// 패턴의 중복되는 부분(수치) 찾기
vector<int> getPi(string pattern) {
    // 모두 0으로 세팅(중복되는 거 모두 없다고 우선 세팅)
    vector<int> p(pattern.length(), 0);
    int correct_cnt = 0;
    for (int i = 1; i < pattern.length(); i++) {
        // 해당 부분이 일치할 시에 일치하는 숫자(correct_cnt)만 증가시키고 p[i]값 set(마지막부분)
        if (pattern[i] == pattern[correct_cnt]) correct_cnt++;
        else {
            // 불일치할 경우 중복되는 만큼(p[correct_cnt-1]의 수치) correct_cnt를 변경 
            // correct_cnt는 1부터, p[i]는 0부터이므로 -1을 해준다
            // 그리고 i-1 하여 다시한번 해당 index를 반복한다.
            if (correct_cnt > 0) {
                correct_cnt = p[correct_cnt - 1];
                i--;
                continue;
            }
            // 만약 correct_cnt가 0이라면 일치하는게 없는 것이므로 그대로 p[i]에 세팅해준다.
        }
        p[i] = correct_cnt;
    }
    return p;
}
 
// KMP 알고리즘
int kmp(vector<int> p, string pattern, string sentence, int start_idx) {
    int correct_cnt = 0;
    int pattern_len = pattern.length();
    for (int i = start_idx; i < sentence.length(); i++) {
        if (sentence[i] == pattern[correct_cnt]) correct_cnt++;
        else {
            if (correct_cnt > 0) {
                correct_cnt = p[correct_cnt - 1];
                i--;
            }
        }
        if (correct_cnt == pattern_len) return i;
    }
    return -1;
}
 
int main(void) {
    string sentence;
    string pattern;
    
    // 띄어쓰기가 있을 경우를 대비해서 getline 사용!
    getline(cin, sentence);
    getline(cin, pattern);
    vector<int> p;
    p = getPi(pattern);
    
    // 총 해당 패턴이 몇개 나왔는지 결과 측정 변수
    int result = 0;
    // 문장에서 문장 검색을 시작할 위치(index)
    int start_idx = 0;
    while (true) {
        int kmp_result = kmp(p, pattern, sentence, start_idx);
        if (kmp_result >= 0) {
            result++;
            start_idx = kmp_result + 1;
        }
        else break;
    }
    cout << result;
    return 0;
}
 

 

질문이나 지적사항은 댓글 부탁드립니다 :)