[백준] 1786번 찾기

1786 찾기

풀이)

KMP 알고리즘을 이용해서 패턴이 문자열에 일치하는 횟수와 인덱스를 출력하는 문제이다.

KMP 알고리즘에 대한 설명 링크

https://comyoung.tistory.com/177

코드)

#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
 
#define MAX 1000003
char T[MAX];
char P[MAX];
int F[MAX];
vector<int> match_idx;
 
int main() {
    char ch;
    int n = 0, m = 0;
    for (int i = 0; i < MAX; i++) {
        ch = getchar();
        if (ch == '\n') break;
        T[i] = ch;
        n++;
    }
    for (int i = 0; i < MAX; i++) {
        ch = getchar();
        if (ch == '\n') break;
        P[i] = ch;
        m++;
    }
    
    //전처리
    F[0] = 0;
    int i = 1;
    int j = 0;
    while (i<m)
    {
        if (P[i] == P[j]) {
            F[i] = j + 1;
            i = i + 1;
            j = j + 1;
        }
        else if (j > 0) {
            j = F[j - 1];
        }
        else {
            F[i] = 0;
            i = i + 1;
        }
    }
 
    //KMP
    i = 0;
    j = 0;
    int result = 0;
    while (i<n)
    {
        if (T[i] == P[j]) {
            if (j == m - 1) {
                match_idx.push_back(i - j);
                result++;
                i = i + 1;
                j = F[j];
            }
            else {
                i = i + 1;
                j = j + 1;
            }
            
        }
        else if (j > 0) {
            j = F[j - 1];
        }
        else {
            i = i + 1;
        }
    }
    printf("%d\n", result);
    for (int i = 0; i < match_idx.size(); i++) {
        printf("%d ", match_idx[i] + 1);
        //+1해주는 이유는 문자열을 인덱스상에서는 배열 0~n-1부터 저장했으니
    }
    return 0;
}