[6. 문자열] 6.12 부분 문자열이 첫 번째로 등장한 위치 찾기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

// main에서 vector 형태로 출력하기위한 기본 셋팅 

---

Q 6.12 부분 문자열이 첫 번째로 등장한 위치 찾기

검색할 문자열 s 와 텍스트 t 가 주어졌을 때, t에서 s가 처음 나타나는 위치를 찾는 프로그램을 작성하시오.

---

평범하게 두개의 중첩된 반복문을 사용하면 시간 복잡도 O(n²)으로 해당 문제를 해결 할 수 있다.
그러나 선형의 시간에 가능하게 하기 위하여 Rabin-Karp 알고리즘을 사용하러고한다.
Rabin-Karp 알고리즘은 Hash를 사용해서 비교하는 알고리즘이다.

해당 내용의 소스코드와 결과는 다음과 같다.

// 6.12 부분 문자열이 첫 번째로 등장한 위치 찾기#include<string>
 
int RabinKarp(const std::string& t, const std::string& s)
{
    if (size(s) > size(t)) //s가 t보다 크면 부분문자열이 될 수 없다.
    {
        return -1;
    }
 
    const int kBase = 26;
    int t_hash = 0, s_hash = 0;
    int power_s = 1;
    for (int i = 0; i < size(s); i++)
    {
        power_s = i ? power_s * kBase : 1;
        t_hash = t_hash * kBase + t[i];
        s_hash = s_hash * kBase + s[i];
    }
    for (int i = size(s); i < size(t); i++)
    {
        if (t_hash == s_hash && !t.compare(i - size(s), size(s), s))
        {
            return i - size(s);
        }
        t_hash -= t[i - size(s)] * power_s;
        t_hash = t_hash * kBase + t[i];
    }
 
    if (t_hash == s_hash && t.compare(size(t) - size(s), size(s), s) == 0)
    {
        return size(t) - size(s);
    }
    return -1;
}

// main std::cout << "6-12 " << RabinKarp("aaaaccabcdddd", "abcd") << std::endl; //6-12

결과