KMP 알고리즘

난이도 하드
자주 묻는 질문 수행자 아마존 구글 MakeMyTrip MAQ Microsoft 신탁 알레그로
패턴 검색 조회수 51

KMP (Knuth-Morris-Pratt) 알고리즘 주어진 패턴 검색에 사용됩니다. . 문자열 S와 패턴 p가 주어지며, 우리의 목표는 주어진 패턴이 문자열에 존재하는지 여부를 결정하는 것입니다.

입력:
S =“aaaab”
p =“aab”
출력:
참된

순진한 접근

패턴 검색에 대한 순진한 접근 방식은 주어진 문자열에서 문자별로 주어진 패턴 문자를 일치시키는 것입니다.

S =“aaaab”-> 일치
p =“a아”

S =“aaaab”-> 일치
p =“aa비"

S =“aaaab”-> 불일치
p =“aab"

S =“aaaab”-> 일치
p =“a아”

S =“aaaab”-> 일치
p =“aa비"

S =“aaaab”-> 불일치
p =“aab"

S =“aaaab”-> 일치
p =“a아”

S =“aaaab”-> 일치
p =“aa비"

S =“아아아b”-> 일치
p =“aab"

패턴 p는 S.
위의 접근 방식에서 불일치가 발생하면 String S의 진행 상황을 되돌리고 있으므로 순진한 패턴 일치 알고리즘의 시간 복잡성은 다음과 같습니다. O (S의 길이 x p의 길이).

KMP 알고리즘

KMP의 아이디어 연산 진행 상황을 저장하고 메인 String (S)에서 되돌리기를 제거하는 것입니다. 이는 주어진 pattern (p)을 사전 처리하여 달성됩니다.
알고리즘은 순진한 접근 방식과 유사합니다. 문자열 S에서 문자별로 pattern_p를 검색하기 시작하고 불일치가 발생하면 기본 문자열 S에서 되 돌리는 대신 패턴 p에서 위치를 되돌립니다. 접미사가 패턴에서 일치하는 부분의 접두사이기도 한 점입니다.

S =“abcaxabcab”-> 일치
p =“abcab”

S =“abcaxabcab”-> 일치
p =“ab택시"

S =“abcaxabcab”-> 일치
p =“abc아”

S =“abcaxabcab”-> 일치
p =“abca비"

S =“abcaxabcab”-> 불일치
p =“abcab"

이 시점에서 문자열 s의 pattern_p와 일치하는 부분은 "abca"입니다.이 일치 부분에서 인덱스 4의 "a"는 접두사 (인덱스 1의 "a")이기도 한 접미사이므로 p에서 다시 되돌립니다. 문자 b (접두사 "a"옆)와 일치를 계속합니다.

S =“abcaxabcab”-> 불일치
p =“ab택시"

패턴의 일치하는 부분

 

문자열 S의 p는 "a"이고 접두사이기도 한 접미사가 없으므로 p의 첫 번째 문자로 되돌리고 KMP 알고리즘을 사용하여 일치를 계속합니다.

S =“abcaxabcab”-> 불일치
p =“abcab”

인덱스 1에서 불일치가 발생 했으므로 문자열 S로 진행합니다.

S =“abcaxabcab”(일치)
p =“abcab”

S =“abcaxabcab”(일치)
p =“ab택시"

S =“abcaxabcab”(일치)
p =“abc아”

S =“abcaxabcab”(일치)
p =“abca비"

S =“abcaxabcab”(일치)
p =“abcab"

KMP 알고리즘

우리는 S에서 p를 찾았습니다.

암호알고리즘

  1. pattern_p의 길이와 같은 크기의 table이라는 배열을 생성합니다. table [i]는 인덱스 1부터 i까지의 접두사이기도 한 가장 긴 접미사의 길이를 저장합니다.
  2. Initialize table [0] = 0, 인덱스 0의 경우 접두사이기도 한 접미사가 없기 때문입니다.
  3. i = 0 및 j = 1을 초기화하고 j <n (pattern_p의 길이) 동안 루프를 실행하고 4 단계와 5 단계를 반복합니다.
  4. p [i]와 p [j]가 일치하면 table [j] = i + 1, i 및 j 증가
  5. p [i]와 p [j]가 일치하지 않고 i가 0과 같지 않으면 i = table [i – 1]이고 i = 0이면 table [j] = 0이고 j를 증가시킵니다.

KMP 알고리즘을위한 의사 코드

table[0] = 0
i = 0, j = 1
while (j < n) { // n is the length of pattern p
    if (p[i] == p[j]) {
        table[j] = i + 1;
        i++;
        j++;
    } else {
        if (i != 0) {
            i = table[i - 1];
            // Do not increment j here
        } else {
            table[j] = 0;
            j++;
    }
}
}

패턴 : "aaab"
표 [] = {0, 1, 2, 0}

패턴 :”dsgwadsgz”
테이블 = {0, 0, 0, 0, 0, 1, 2, 3, 0}

암호알고리즘

  1. 위에서 언급 한대로 패턴을 사전 처리하여 접두사-접미사 테이블 배열을 만듭니다.
  2. 첫 번째 문자부터 시작하여 주어진 문자열과 패턴을 일치시키기 시작하고 모든 문자와 일치하면 패턴이 발견되고 중지 될 때까지 두 문자열에서 계속 증가합니다.
  3. 불일치가 발생하면 패턴의 인덱스 i에서 불일치가 발생하도록하고, 패턴의 테이블 [i – 1] 인덱스로 되돌 리거나 인덱스 0에서 불일치가 발생하면 인덱스 0으로 되돌립니다.
  4. 전체 문자열을 횡단하거나 패턴을 찾을 때까지 2 단계와 3 단계를 반복합니다.

KMP 알고리즘 용 JAVA 코드

public class KMPAlgorithm {
    // Function to pre-process the pattern and to create the suffix-prefix table
    private static void preProcess(char[] p, int[] table, int n) {
        // Initialize table[0] as 0
        table[0] = 0;
        // Initialise i = 0 and j = 1
        int i = 0, j = 1;
        // Run a loop till length of pattern, if p[i] and p[j] matches table[j] = i + 1 else table[j] = 0
        while (j < n) {
            if (p[j] == p[i]) {
                // Match found set table[i] = i + 1, and advance i and j
                table[j] = i + 1;
                i++; j++;
            } else {
                if (i != 0) {
                    i = table[i - 1];
                    // We do not increment j here
                } else {
                    table[j] = 0;
                    j++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char S[] = "abcaabcab".toCharArray();
        char p[] = "abcab".toCharArray();

        // Pre-process the pattern
        int table[] = new int[p.length];
        preProcess(p, table, p.length);

        // Searching the pattern in the given string
        int i = 0; // index for string
        int j = 0; // index for pattern
        boolean found = false; // Boolean variable to indicate that the pattern is found or not
        
        while (i < S.length) {
            if (S[i] == p[j]) {
                // Advance forward the characters are same
                i++;
                j++;
            } else {
                // Characters are not same, revert back the progress in the pattern
                if (j !=0) // Reset the position of j in the pattern, do no advance in string
                    j = table[j - 1];
                else // first character is mis-matched, advance in the string
                    i++;
            }

            if (j == p.length) {
                // The pattern is found in the string
                found = true;
                break;
            }
        }
    
        if (found)
            System.out.println("true");
        else
            System.out.println("false");
     }
}
true

KMP 알고리즘 용 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
void preProcess(char *p, int *table, int n) { 
    // Initialize table[0] as 0 
    table[0] = 0;
    // Initialise i = 0 and j = 1
    int i = 0, j = 1;
    // Run a loop till length of pattern, if p[i] and p[j] matches table[j] = i + 1 else table[j] = 0
    while (j < n) {
        if (p[i] == p[j]) {
            // Match found set table[i] = i + 1, and advance i and j
            table[j] = i + 1;
            i++; 
            j++;
        } else {
            if (i != 0) {
                i = table[i - 1];
                // We do not increment j here
            } else {
                table[j] = 0;
                j++;
            }
        }
    } 
} 

int main() {
    char s[] = "abcaabcab";
    char p[] = "abcab";
    int n = strlen(s);
    int m = strlen(p);
    
    // Pre-process the pattern
    int table[m];
    preProcess(p, table, m);
    
    // Searching the pattern in the given string
    int i = 0;      // index for string 
    int j = 0;      // index for pattern
    bool found = false; // Boolean variable to indicate that the pattern is found or not
    while (i < n) {
        if (s[i] == p[j]) {
            // Advance forward the characters are same
            i++; 
            j++;
        } else {
            // Characters are not same, revert back the progress in the pattern 
            if (j != 0)  {
                // Reset the position of j in the pattern, do no advance in string  
                j = table[j - 1];
            } else {
                // first character is mis-matched, advance in the string
                i++;
            }
        }
        
        if (j == m) {
            // The pattern is found in the string
            found = true;
            break;
        }
    }
    if (found)
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
    
    return 0; 
}
true

KMP 알고리즘의 복잡성 분석

KMP 알고리즘에서는 문자열 S에서 되 돌리는 것이 없으므로 시간 복잡도는 S 길이의 순서이며 전처리를 위해 pattern_p의 길이에 비례합니다.

시간 복잡성 = O (문자열 S의 길이 + 패턴 p의 길이)

참조

Translate »