큰소리 kmp!(모드 테스트 문제 hdu 1171)

kmp 는 데이터 구조 에서 문자열 에 관 한 중요 한 내용 입 니 다. kmp 에 관 한 것 입 니 다. 인터넷 에 많은 자료 가 있 지만 어떤 사람 은 보고 알 아 보 았 습 니 다. 어떤 사람 은 보고 도 모 르 기 때문에 저 는 스스로 정리 해 야 합 니 다.
kmp 에서 next 배열 을 구 하 는 것 은 가장 어 려 운 것 입 니 다. 특히 그 k = next [k] 는 정말 이해 하기 어렵 습 니 다. 우선, kmp 의 효율 적 인 이 유 는 예비 처 리 를 한 다음 에 일치 할 때 메 인 문자열 이 거 슬러 올 라 가지 않 아 kmp 효율 이 O (n + m) 에 이 르 렀 기 때 문 입 니 다. 일반적인 폭력 보다 훨씬 효율 적 입 니 다.
우선 get 분석 을 해 보도 록 하 겠 습 니 다.next 함수, 이것 은 next 배열 을 얻 는 함수 입 니 다.i 의 의 미 는 next [i + 1] 의 값 을 구 하 는 것 입 니 다. j 의 의 미 는 이전 next [] 의 값 이 얼마 입 니까? 예 를 들 어 이전 j 는 5 이 고 이때 t [i] = t [j] 는 바로 이때 의 next [i + 1] = = 6 을 나타 내 는 것 입 니 다. next 배열 은 가장 긴 접두사 접 두 사 를 나타 내기 때 문 입 니 다.
j = = - 1 일 때, next [i] = 0, 이것 은 이해 하기 어렵 지 않다.t [i] = = t [j] 때 가 더 좋 고 바로 + 1 입 니 다.t [i] = = t [j] 일 때 이 답 은 0 일 수도 있 고 0 ~ j - 1 사이 일 수도 있 습 니 다. 어차피 j 를 넘 지 않 을 것 입 니 다. 유일 하 게 j + 1 과 같은 기 회 는 이미 놓 쳤 기 때 문 입 니 다 (t [i] = t [j]). 그래서 우 리 는 어떻게 선택해 야 합 니까? 그래서 선배 들 은 k = next [k] 라 는 자 리 를 선택 하 라 고 했 습 니 다!
왜?http://www.rudy-yuan.net/archives/182/ 나 도 말 하고 싶 은 데 이 블 로 그 는 아주 분명하게 말 했다. 나 는 수첩 에 있 는 그림 이 너무 못 생 겨 서 정말 잘 보이 지 않 는 다. 바로 이 블 로 그 를 보 자!

void get_Next(int m){
    next_[0]=-1;
    for(int i=0,j=-1;i<m;){
        if(j==-1||t[i]==t[j]){
            i++;j++;
            next_[i]=j;
        }
        else j=next_[j];
    }

    /*
    int j=0,k=-1;
    while(j<m){
        while(k>=0&&t[j]!=t[k]){
            k=next_[k];
        }
        j++;k++;
        next_[j]=k;
    }
    */
}

여기 getnext 함수 와 아래 주석 부분의 표기 법 은 모두 같 습 니 다.

int kmp_solve(int n,int m){
    get_Next(m);
    int i=0,j=0;
    while(i<n&&j<m){
        if(s[i]==t[j]){
            i++;j++;
        }
        else if(next_[j]==-1){
            i++;
        }
        else j=next_[j];
    }
    if(j>=m)return i-j+1;
    return -1;
}

else if (next [j] = - 1) 라 는 말 을 볼 수 있 습 니 다. 인터넷 코드 와 다른 것 을 발견 할 수 있 습 니 다. 물론 여기 서 많은 사람들 이 j = = 0 이 라 고 썼 습 니 다. 여기 서 이렇게 쓰 면 더 이해 할 수 있 을 것 같 습 니 다.사실은 모두 똑 같 습 니 다. 우리 가 next 를 구 하 는 코드 에 따라 next [i] 를 계산 할 때 j 는 + + 가 지나 간 것 입 니 다. 이것 은 j = = 0 을 제외 하고 다른 next 값 이 - 1 일 수 없다 는 것 을 의미 합 니 다. 그러나 저 는 이렇게 썼 습 니 다. 우 리 는 다음 에 next [j] 의 값 을 j 에 게 부여 해 야 하기 때문에 우 리 는 j = = - 1 의 상황 을 배열 하여 실 수 를 방지 하 는 것 으로 이해 할 수 있 습 니 다.물론 이것 은 이해 일 뿐 입 니 다. 정확 하고 공식 적 으로 신 복 력 이 있 는 해답 은 이 문 구 는 s [i] 와 t [0] 가 기다 리 고 싶 지 않 으 면 i 는 직접 + + 할 수 있 습 니 다. j 의 위 치 를 조정 하지 않 아 도 됩 니 다. i 위치 에 대해 t 꼬치 는 기다 리 고 싶 지 않 기 때문에 다음 매 칭 을 직접 할 수 있 습 니 다.
코드 쓰기: (이 코드 는 hdu 1171 코드, 순수 kmp 모드)

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>

const int maxn=1000005;
int s[maxn];
int t[maxn];
int next_[maxn];

void get_Next(int m){
    next_[0]=-1;
    for(int i=0,j=-1;i<m;){
        if(j==-1||t[i]==t[j]){
            i++;j++;
            next_[i]=j;
        }
        else j=next_[j];
    }

    /*
    int j=0,k=-1;
    while(j<m){
        while(k>=0&&t[j]!=t[k]){
            k=next_[k];
        }
        j++;k++;
        next_[j]=k;
    }
    */
}

int kmp_solve(int n,int m){
    get_Next(m);
    int i=0,j=0;
    while(i<n&&j<m){
        if(s[i]==t[j]){
            i++;j++;
        }
        else if(next_[j]==-1){
            i++;
        }
        else j=next_[j];
    }
    if(j>=m)return i-j+1;
    return -1;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
        }   
        for(int i=0;i<m;i++){
            scanf("%d",&t[i]);
        }
        int ans;
        if(n>=m)
             ans=kmp_solve(n,m);
        else ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}