KMP 알고리즘(문자열 비교)

"Is there a (longest) suffix which is also a prefix?" (접미사 중에서 접두사와 일치하는 가장 긴 것이 있는가?)

---

▶KMP 알고리즘 설명

- 문자열 검색 알고리즘, O(N + M).

- N : 텍스트 길이, M : 패턴 길이

- 두 단계로 나뉜다.

 

1. KMP Substring(=pattern) Search, O(m)

ABCDABCDABEE

ABCDABE

를 비교하였을 때 매칭되지 않는 시점(C != E) 바로 직전의 접미사(suffix) 중에서

접두사(prefix)와 일치하는 가장 긴 길이는 얼마인가?

 

==> 정답 : 2

결과는 테이블 형태로 나타내는데 길이는 패턴 길이와 동일하다.

위의 예시에서 테이블은 [0 0 0 0 1 2] 이 된다.

 

(코드)

vector<int> makeTable(string pattern) //Substring Search
{
    int patternSize = pattern.size();
    vector<int> table(patternSize, 0);
    int j = 0;
    for (int i = 1; i < patternSize; i++)
    {
        while (j > 0 && pattern[i] != pattern[j]) //만약 일치하지 않는다면,
            j = table[j - 1];                     //일치했던 부분까지 되돌아 간다.
        
        if(pattern[i] == pattern[j])  //일치하면 j가 증가하게 되고
            table[i] = ++j;           //for문에 의해 i도 증가하게 된다.
    }
    return table;
}

 

따라서 다음번 비교시에는 '패턴'의 접미사(prefix)를 비교했던 텍스트의 접두사(suffix)에 곧장 옮겨서 비교한다.

 

2. String search, O(n)

- 위에서 구한 테이블을 활용해 텍스트와 패턴을 비교한다.

즉, O(m) + O(n) --> O(m + n)

 

---

(전체 코드)

- point1, 2를 눈여겨 보자

//O(n)
vector<int> kmp(string s, string p)
{
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j = 0;
    
    for(int i = 0; i<n; i++)
    {
    	while(j > 0 && s[i] != p[j])   // ★point1
            j = pi[j - 1];
        if(s[i] == p[j])
        {
            if(j == m - 1)
            {
            	ans.push_back(i-m+1);
                j = pi[j];
            }
            else
            {
            	j++;
            }
        }
    }
    return ans;
}

//O(m)
vector<int> makeTable(string pattern) //Substring Search
{
    int patternSize = pattern.size();
    vector<int> table(patternSize, 0);
    int j = 0;
    for (int i = 1; i < patternSize; i++)
    {
        while (j > 0 && pattern[i] != pattern[j]) // ★point2
            j = table[j - 1];
        
        if(pattern[i] == pattern[j])
            table[i] = ++j;
    }
    return table;
}


/*
s : ABABABABBABABABABC
p : ABABABABC	
*/
int main()
{
	string s, p;
    getline(cin, s); 
    getline(cin, p);
    auto matched = kmp(s,p);
    printf("%d\n", (int)matched.size());
    
    for(auto i : matched) 
    	printf("%d ", i+1); 
        
    return 0; 
}

 

---

출처

www.youtube.com/watch?v=GTJr8OvyEVQ

bowbowbow.tistory.com/6