C#에서 KMP 알고리즘을 구현하는 방법

C#에서 KMP 알고리즘을 구현하는 방법

KMP(Knuth-Morris-Pratt) 알고리즘은 텍스트 문자열에서 패턴 문자열의 위치를 ​​찾는 데 사용되는 효율적인 문자열 일치 알고리즘입니다. 핵심 아이디어는 불필요한 비교를 피하기 위해 일치된 부분 정보를 사용하는 것입니다.

KMP 알고리즘 구현의 핵심은 다음 배열이라고도 불리는 부분 일치 테이블(Partial Match Table)을 구축하는 것입니다. 이 배열은 패턴 문자열의 각 접두사 하위 문자열에 대해 가장 긴 일치 접미사 하위 문자열의 길이를 기록합니다.

다음은 C#에서 KMP 알고리즘을 구현하기 위한 구체적인 단계와 코드 예제입니다.

1단계: 부분 일치 테이블 구축

1. 다음에 패턴 문자열 길이의 크기로 정수 배열을 정의하고 초기화합니다. 다음[0] = -1 .
2. 초기값이 각각 0과 -1인 두 개의 포인터 i와 j를 정의합니다.
3. i가 패턴 문자열의 끝에 도달했는지 확인하고 그렇지 않은 경우 다음 단계를 수행합니다.
   a. j가 -1과 같거나 현재 문자가 포인터 j에 해당하는 문자와 같으면 i와 j는 다음과 같습니다. 동시에 뒤로 이동하고 next[i ] = j입니다.
   b. 그렇지 않으면 포인터 j를 next[j] 위치로 이동하고 계속 일치시킵니다.
4. 다음에 구성된 부분 일치 테이블을 반환합니다.

위 단계를 구현하는 방법에 대한 코드는 다음과 같습니다.

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

2단계: 일치를 위해 부분 일치 테이블 사용

1. 텍스트 문자열과 패턴의 시작 위치를 가리키는 두 개의 포인터 i와 j를 정의합니다. 각각 문자열.
2. i와 j가 끝에 도달했는지 확인합니다. 그렇지 않은 경우 다음 단계를 수행합니다.
   a. j가 -1이거나 현재 문자가 포인터 j에 해당하는 문자와 같으면 i와 j가 이동합니다. 동시에 뒤로.
   b. 그렇지 않으면 포인터 j를 next[j] 위치로 이동하고 계속 일치시킵니다.
3. 포인터 j가 패턴 문자열의 끝을 가리키면 일치에 성공한 것이며 텍스트 문자열의 시작 위치 인덱스가 반환된다는 의미입니다.
4. 경기가 실패하면 -1이 반환됩니다.

위 단계를 구현하는 방법에 대한 코드는 다음과 같습니다.

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

KMP 메소드를 호출하고 텍스트 문자열과 패턴 문자열을 전달하면 일치하는 결과를 얻을 수 있습니다.

위는 C#에서 KMP 알고리즘을 구현하는 방법에 대한 단계와 코드 예제입니다. 부분 일치 테이블을 활용함으로써 KMP 알고리즘은 특히 큰 텍스트 문자열과 긴 패턴 문자열을 처리할 때 더 나은 성능으로 문자열 일치 효율성을 효과적으로 향상시킬 수 있습니다.

위 내용은 C#에서 KMP 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!