[SWEA] 4038. 단어가 등장하는 횟수 (C++, 라이브러리 X)

August 10, 2021

Algorithm 카테고리의 다른 글

👉 [SWEA] 12526. 자동완성 (C++, 라이브러리 X) 2021-08-19

👉 [SWEA] 7091. 은기의 아주 큰 그림 (C++, 라이브러리 X) 2021-08-12

👈 [SWEA] 4038. 단어가 등장하는 횟수 (C++, 라이브러리 X) 2021-08-10

👉 [SWEA] 2948 문자열 교집합 (C++, 라이브러리 X) 2021-08-10

👉 [SWEA] 3813 그래도 수명이 절반이 되어서는… (C++, 라이브러리 X) 2021-08-10

Hash 기본문제

풀이

Hash를 사용하지 않고 KMP 알고리즘을 사용했습니다.

참고: KMP : 문자열 검색 알고리즘

실수

테스트 케이스를 여러번 실행할 때에는 전역변수 초기화를 잘 해줄 것.

코드 GitHub

#include <iostream>
using namespace std;

#define MAXB 500001
#define MAXS 100001

char B[MAXB], S[MAXS];
int P[MAXS];

void CalcP() {
    P[0] = 0;
    for(int i = 1; S[i]; i++) {
        int j = P[i-1];
        while(j > 0) {
            if(S[i] == S[j]) break;
            j = P[j-1];
        }
        if(S[i] == S[j]) P[i] = j + 1;
        else P[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for(int tc = 1; tc <= T; tc++) {
        cin >> B >> S;
        CalcP();

        int piv = 0, cnt = 0, ans = 0;
        while(B[piv]) {
            if(B[piv] == S[cnt]) {
                if(!S[cnt+1]) {
                    // Find
                    ans++;
                    cnt = P[cnt];
                } else cnt++;
                piv++;
            } else if(cnt > 0) cnt = P[cnt-1];
            else piv++;
        }
        cout << '#' << tc << ' ' << ans << '\n';
    }
    return 0;
}