문자열 일치 알고리즘 KMP 상세 설명

문자열 일치 알고리즘 KMP 상세 설명
RT, 오늘 은 매우 지루 합 니 다. 물 문 제 를 풀 었 습 니 다. 물 문 제 를 푸 는 과정 에서 도 많은 문 제 를 발 견 했 습 니 다. 다음은 KMP 에 대해 작은 설명 을 하 겠 습 니 다.
의 원리
우선 KMP 는 문자열 일치 알고리즘 입 니 다. 이것 은 주 에 알려 져 야 합 니 다.그것 의 사고방식 은 아마도 패턴 문자열 에 대해 상태 기와 유사 한 것 을 구성 하고 그 어 울 리 지 않 는 함수 와 어 울 리 지 않 는 변 을 구성 한 다음 에 문자열 이 일치 할 때 신속하게 이동 하 는 알고리즘 이다
어 울 리 지 않 는 함 수 를 구성 할 때 자신 이 자신 과 일치 하 는 것 이 라 고 매우 오도 하 는 표현 이 있다. 이것 은 약간 느낌 이 있 지만 사실은 학습 에 도움 이 되 지 않 고 새로운 문제 에 대처 하 는 것 일 뿐이다.
사실은 관찰 성격 을 통 해 전달 하 는 과정 으로 인터넷 관련 자료 가 이미 많 음 을 감안 하여 구체 적 인 과정 은 코드 를 참고 할 수 있다.
코드

#include
#include
#include
#include
#define maxn1 1000005
#define maxn2 10005
using namespace std;
char txt[maxn1],tem[maxn2];
int len1,len2,ans=0;
int f[maxn2];
void init(){
    len1=strlen(txt);
    len2=strlen(tem);
    f[0]=f[1]=0;
    for(int i=2;i<=len2;i++){
        int k=f[i-1];
        while(k!=0&&tem[k]!=tem[i-1]) k=f[k];
        f[i]=(tem[k]==tem[i-1])?k+1:0;//         
    }
    return;
}
void KMP(){
    int pos=0;
    for(int i=0;iwhile(pos!=0&&txt[i]!=tem[pos]){
            pos=f[pos];
        }
        if(txt[i]==tem[pos])
            pos++;
        if(pos==len2){
            pos=f[pos];
            ans++;
        }//    ，       f[len2]
    }
}
int main(){
    /*freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s
%s",tem,txt);
        init();
        KMP();
        printf("%d
",ans);
        ans=0;
    }
    return 0;
}

세부 사항
주로 다음 과 같다.
1. 위 에서 말 한 것 처럼 그곳 의 k + 1 은 틀 리 면 안 됩 니 다. 2. 일치 할 때의 편 의 를 위해 우 리 는 추가 f [len2] 를 계산 하여 성공 후의 이동 에 편리 하도록 할 수 있 습 니 다.
활용 단어 참조
응용 프로그램 에서 가장 흔히 볼 수 있 는 것 은 O (n) 시간 내 에 문자열 일치 결 과 를 구 하 는 것 입 니 다. 그러나 문자열 의 모든 Border 를 빠르게 구 하 는 데 도 사용 할 수 있 습 니 다. 모 르 면 시간 이 있 더 라 도 보충 할 수 있 습 니 다.
예제
기본적으로 모두 몇 개의 물 문제 이 고, 아래 는 쇠사슬 로 문 제 를 풀 것 이다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

알고리즘 - Knuth, Morris, Prett

흔히 찾는 문자나 문자열이 있는 지 없는 지를 확인할 때는 주로 if pattern in words 이런 식으로 검사를 할 수 있다. pi 테이블은 찾으려는 문자열(pattern)의 정보를 저장하고 있는 배열, 자료...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

문자열 일치 알고리즘 KMP 상세 설명

좋은 웹페이지 즐겨찾기