[BOJ] 찾기_1786 C++ 풀이

문제

첫째 줄에 문자열 T가 주어지고 두번째 줄에 부분 문자열 P가 주어진다. T와 P는 알파벳 대소문자와 공백으로만 이루어져 있다. 이때 T문자열에 P부분 문자열이 총 몇번 일치하고 어느 위치에서 일치 하는지를 출력하는 문제이다.

접근 방법

기본적으로 문자열 매칭과 관련된 문제이므로 KMP 알고리즘을 활용하는 쪽으로 접근해 보았다. 최대일치길이를 표현하는 테이블을 반환해 주는 makeTable 함수와 KMP 알고리즘을 실행하는 KMP 함수를 선언하여 활용하였다.

KMP 함수 내에서 부분 문자열 P와 일치하는 문자열을 찾았다면 일치하는 문자열의 시작 지점을 ans 배열에 저장하였다.

하지만 이 문제에서 해맸던 부분은 바로 이 문자열이 일치하기 시작하는 지점을 구하는 것이었다. 결과적으로 이 지점은 KMP 함수내에서 i-patternSize+2로 표현이 가능한데 그 이유는 문자열 에서 부분 문자열이 일치한다는 것을 알아 냈다면 i는 문자열의 일치하는 부분문자열에 해당하는 끝 부분에 위치하여 매칭하는지 검사를 마쳤을 것이다. 하지만 우리가 찾는 건 일치하기 시작하는 지점이므로 i에서 부분 문자열의 길이에 해당하는 patternSize 만큼 빼주는 것이다.

뒤에 2를 추가로 더해주는 이유는 KMP 함수의 for문에서 i=0으로 시작했기 때문에 i-patternSize의 결과는 -1이 나오기 때문이다. 또한 문제에서 문자의 위치를 0이 아닌 1부터 새기 때문에 +2를 하는것이다.

구현

#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> ans;

vector<int> makeTable(string pattern)
{
    int j=0;
    int patternSize=pattern.size();
    vector<int> table(patternSize, 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 str, string pattern)
{
    int j=0;
    int patternSize=pattern.size();
    int strSize=str.size();
    vector<int> table = makeTable(pattern);

    for(int i=0; i<strSize; i++)
    {
        while(j>0 && str[i]!=pattern[j])
            j=table[j-1];
        
        if(str[i] == pattern[j])
        {
            if(j==patternSize-1)
            {
                ans.push_back(i-patternSize+2);
                j=table[j];
            }
            else
                j++;
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string str, pattern;
    getline(cin, str);
    getline(cin, pattern);

    KMP(str, pattern);
    int len=ans.size();

    cout<<len<<'\n';

    for(int i=0; i<len; i++)
        cout<<ans[i]<<' ';
    
    return 0;
}

BOJ_찾기