데이터 구조 - 문자열 의 패턴 일치 알고리즘
2121 단어 데이터 구조
물론 현재 의 방법 은 모두 완벽 하 게 포장 되 어 있 습 니 다. 우 리 는 하나의 메 인 문자열 에서 하나의 키 문자열 로 위 치 를 정 해 야 합 니 다. 간단 한 indexof 방법 은 충분히 실현 할 수 있 습 니 다.그래서 오늘 은 문 제 를 어떻게 해결 하 는 지 는 물론 이 고 일치 하 는 원 리 를 살 펴 보 자.두 문자열 의 일치 문제 에 대해 서 는 잠시 배열 로 이 루어 집 니 다.
다음은 소박 한 패턴 매 칭 법 을 살 펴 보면 우리 가 가장 이해 하기 쉬 운 알고리즘 일 것 이다.
/* */
int Index(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (S[i] == T[j]) /* */
{
++i;
++j;
}
else /* */
{
i = i-j+2; /* i */
j = 1; /* j T */
}
}
if (j > T[0])
return i-T[0];
else
return 0;
}코드 의 측면 에서 볼 때 위의 소박 한 일치 알고리즘 은 반복 적 으로 옮 겨 다 니 는 현상 이 뚜렷 하기 때문에 효율 이 약간 떨어진다.그래서 반복 되 는 상황 을 피하 기 위해 또 하나의 패턴 매 칭 알고리즘 이 하늘 로 떠 올 랐 다. 우 리 는 크 누 트 - 모 리 스 - 프 라 트 알고리즘 이 라 고 부 르 는데 KMP 알고리즘 이 라 고 부른다.다음은 KMP 알고리즘 을 살 펴 보 겠 습 니 다.
/* T S pos 。 ， 0。 */
/* T ，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos)
{
int i = pos; /* i S ， pos 1， pos */
int j = 1; /* j T */
int next[255]; /* next */
get_next(T, next); /* T ， next */
while (i <= S[0] && j <= T[0]) /* i S j T ， */
{
if (j==0 || S[i] == T[j]) /* ， j=0 */
{
++i;
++j;
}
else /* */
j = next[j];/* j ，i */
}
if (j > T[0])
return i-T[0];
else
return 0;
}KMP 알고리즘 코드 에서 저희 가 get 을 사용 한 걸 봤 어 요.next 방법, 즉 next 배열 을 계산 하 는 데 사 용 됩 니 다. 사실 KMP 알고리즘 의 핵심 절 차 는 next 함 수 를 계산 하 는 것 입 니 다. 그러면 next 함 수 를 어떻게 계산 하 는 지 보 세 요. 데이터 구조 - KMP 알고리즘 에서 next 함수 에 대한 상세 한 해석
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
