[SW Expert Academy] 1213. String

[SW Expert Academy] 1213. String

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14P0c6AAUCFAYi&categoryId=AV14P0c6AAUCFAYi&categoryType=CODE

나의 풀이

String에서 특정 단어를 찾는 알고리즘은 아래와 같이 분류할 수 있다.

1. 고지식한 검색

2. 라빈카프

3. KMP

4. 보이어-무어

나는 라빈카프 방식과 KMP 방식으로 풀어보았다.

라빈카프 : 찾을 단어의 HASH 값을 이용하여 동일한 HASH 값을 갖는 단어를 찾는다. O(N)

KMP : 찾을 단어의 접두사와 접미사가 동일한 길이를 저장한 벡터를 이용하여, 탐색 범위를 줄일 수 있다. O(N+M)

나의 코드

GIthub : https://github.com/j2wooooo/Daliy_Algorithms/tree/master/Daliy_Algorithms/SW_Expert_Academy_1213

// // [SW Expert Academy] 1213. String
// 라빈 카프 방식으로 풀이
#include<iostream>
#include<string>
using namespace std;
#define BASE 8
 
int n, ans;
string sentence;
string pattern;
 
long long calchash(string s)
{
    long long sum = 0;
    for (int i = 0; i < (int)pattern.size(); i++)
    {
        sum = (sum << BASE) + s[i];
    }
    return sum;
}
long long findnewhash(int s, int e, int high, long long prehash)
{
    return (prehash - (sentence[s] << (BASE*high)) << BASE) + sentence[e];
}
int main(void)
{
    int T = 10;
    while (T--)
    {
        cin >> n;
        cin >> pattern >> sentence;
        ans = 0;
 
        long long phash = calchash(pattern);
        long long shash = calchash(sentence);
        int psize = (int)pattern.size();
 
        for (int i = 0; i <= (int)sentence.size() - psize; i++)
        {
            shash = findnewhash(i, i + psize, psize-1, shash);
            if (shash == phash) ans++;
        }
        cout << '#' << n << ' ' << ans << '\n';
    }
    return 0;
}

// [SW Expert Academy] 1213. String
// KMP 방식으로 코딩
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int num, ans;
string sentence, pattern;
 
vector<int> makeTable()
{
    int size = (int)pattern.size();
    vector<int> table(size, 0);
 
    int j = 0;
    for (int i = 1; i < size; i++)
    {
        while (j != 0 && pattern[i] != pattern[j])
        {
            j = table[j - 1];
        }
        if (pattern[i] == pattern[j])
        {
            table[i] = ++j;
        }
    }
    return table;
}
int kmp()
{
    vector<int>t = makeTable();
    int ssize = (int)sentence.size();
    int psize = (int)pattern.size();
    int ans = 0;
    int j = 0;
    for (int i = 0; i < ssize; i++)
    {
        while (j != 0 && pattern[j] != sentence[i])
        {
            j = t[j - 1];
        }
        if (pattern[j] == sentence[i])
        {
            if (j == psize - 1)
            {
                ans++;
                j = t[j];
            }
            else
                j++;
        }
    }
    return ans;
}
int main()
{
    int T = 10;
    while (T--)
    {
        cin >> num;
        cin >> pattern;
        cin >> sentence;
        ans = kmp();
 
        cout << '#' << num << ' ' << ans << '\n';
    }
 
    return 0;
}