6-1 단어가 등장하는 횟수

독서광 동철이 책

책에서 어떤 단어가 몇 번 등장하는지 물어봄

책의 내용 비가 주어질 때 특정 단어 에스가 등장하는 횟수를 알아내시오

책의 내용에서 특정 단어가 등장하는 부분이 중첩될 수도 있음에 유의 

const int MAXN = 500000;
const int MAXM = 100000;

unsigned long long d[MAXM / 2 + 5];
//
//unsigned long long my_pow(unsigned long long base, unsigned long long exp)
//{
//    if (exp == 0) return 1;
//    if (exp == 1) return base;
//
//    if (exp % 2 == 0)
//        return my_pow(base * base, exp / 2);
//    else
//        return base * my_pow(base * base, exp / 2);
//}
//
//int myStrlen(char str[])
//{
//    int len = 0;
//    while (str[len]) len++;
//    return len;
//}
//unsigned long long Hash(char str[], int size)
//{
//    unsigned long long res = 0;
//    for (int i = 0; i < size; i++)
//        res += str[i] * d[size - i];
//
//    return res;
//}

int FindString(int N, char *A, int M, char *B)
{
    int ans = 0;
    unsigned long long ah = 0;
    unsigned long long bh = 0;
    unsigned long long pow = 1;

    //Hash를 이용한 문자열 비교
    for (int i = 0; i <= N - M; i++)
    {
        //패턴의 길이만큼 읽어서 해시값 비교
        if (i == 0)
        {
            for (int j = 0; j < M; j++)
            {
                ah = ah + A[M - j - 1] * pow;
                bh = bh + B[M - j - 1] * pow;
                if (j < M - 1) pow = pow * 257;
            }
        }
        else //첫 부분 문자열 이후부터는 계산으로 해시값 구함
            ah = 257 * (ah - A[i - 1] * pow) + A[i + M - 1];

        if (ah == bh) ans++;
    }
    return ans;
}

- 간단하게 해시 하나로 풀리는 문제인가
- 해시를 어떻게 만드는지 쉬운 문제 체크하기
- 오케이 해쉬로 했을 때 빅오가 어떻게 되는지 확인하기