[C++] 백준/Platinum/1786. 찾기

문제: 찾기 (백준 1786번)

문제 개요

목표

주어진 텍스트 문자열에서 패턴 문자열이 등장하는 모든 위치(인덱스)를 찾아, 등장 횟수와 위치를 출력하는 문제.

핵심 포인트

• 단순 문자열 검색(브루트포스)은 O(n×m) 시간 복잡도를 가짐
• KMP (Knuth-Morris-Pratt) 알고리즘을 사용하여 O(n+m) 시간에 해결

1. 패턴 접두사 함수 (KMP 함수)

목적

패턴 문자열 내부에서 각 인덱스까지의 부분 문자열이 가지는 최대 접두사-접미사 일치 길이를 pi 배열에 저장

예시 "ABABC"

인덱스	부분 문자열	접두사-접미사 분석	pi[i]
0	"A"	접두사 길이 0	0
1	"AB"	"B"와 "A" 다름	0
2	"ABA"	"A" (인덱스 2)와 "A" (인덱스 0) 일치	1
3	"ABAB"	인덱스 3의 'B'와 인덱스 1의 'B' 일치	2
4	"ABABC"	불일치로 인해 재조정	0

KMP 접두사 함수 구현

void Kmp(string& pat)
{
    int n = pat.size();
    pi.resize(n, 0);
    int j = 0;
    for (int i = 1; i < n; i++)
    {
        while (j > 0 && pat[i] != pat[j])
        {
            j = pi[j - 1];
        }
        if (pat[i] == pat[j])
        {
            j++;
        }
        pi[i] = j;
    }
}

주요 로직 설명

• while문: 불일치 시 이전 접두사 길이로 돌아가 재비교
• if문: 문자 일치 시 j 증가
• pi[i] = j; 현재 인덱스까지 일치한 접두사의 최대 길이 저장

2. 텍스트 내 패턴 매칭 (KMP 검색)

목적

텍스트 문자열 내에서 패턴이 나타나는 모든 위치 찾기

예시 시나리오

• 텍스트: "ABABABCABABABC"
• 패턴: "ABABC"

매칭 동작 과정

1. 텍스트 순회 중 매칭 상태
   • j 변수를 사용해 패턴과의 매칭 상태 유지
   • 불일치 발생 시 pi 배열을 통해 효율적으로 재검색

KMP 검색 구현

int main()
{
    int n = str.size();
    int m = pat.size();
    int j = 0;
    vector<int> answer;

    for (int i = 0; i < n; i++)
    {
        while (j > 0 && str[i] != pat[j])
        {
            j = pi[j - 1];
        }
        if (str[i] == pat[j])
        {
            j++;
        }
        if (j == m) // 패턴 전체 매칭
        {
            answer.push_back(i - m + 2); // 1-indexed 위치 저장
            j = pi[j - 1];
        }
    }

    // 결과 출력
    cout << answer.size() << '\n';
    for (const int& pos : answer)
    {
        cout << pos << ' ';
    }
}

주요 로직 설명

• while문: 텍스트와 패턴 문자 불일치 시 pi 값으로 j 조정
• if문: 문자 일치 시 j 증가
• 패턴 완전 매칭 시:
  • 시작 위치를 answer 벡터에 저장
  • j를 재조정하여 연속된 매칭 탐색