KMP 알고리즘 의 가장 쉬 운 이해(소 백 튜 토리 얼)

설명 하 다.
KMP 알고리즘 은 이해 하기 가 매우 간단 하고 생각 이 간단 하 며 이해 하기 전에 각종 자 료 를 찾 아 보고 흐리멍덩 하 게 보 았 습 니 다.인터넷 에서 가장 간단 한 해석 을 하 더 라 도 흐리멍덩 하 게 보 았 습 니 다.
나 는 이 물건 이 도대체 무엇 인지 가장 짧 은 편폭 으로 대충 알 아 내 는 데 반나절 이 걸 렸 다.
여 기 는 개념 을 떠 나 알고리즘 과정 과 코드 이해 만 을 말 합 니 다.
KMP 알고리즘
문자열 이 일치 합 니 다.두 문자열 을 드 리 겠 습 니 다.한 문자열 이 다른 문자열 을 포함 하고 있 는 지 찾 으 십시오.포함 되 어 있 으 면 시작 위 치 를 되 돌려 줍 니 다.
다음 두 문자열 과 같이:

char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";

str 는 ptr 를 포함 하 는 두 곳 이 있 습 니 다.
str 의 아래 에 각각 10,26 곳 에 ptr 를 포함 합 니 다.
“bacbababadababacambabacaddababacasdsd”;\

문제 의 유형 은 매우 간단 하 니,다음은 직접 알고리즘 을 소개 한다.
알고리즘 설명
일반적으로 문자열 과 일치 할 때 우 리 는 대상 문자열 str(길이 가 n 이 라 고 가정)의 첫 번 째 하 표 에서 ptr 길이(길이 가 m)와 같은 하위 문자열 을 선택 하여 비교 합 니 다.같 으 면 시작 부분의 하 표 값 을 되 돌려 줍 니 다.다 르 면 str 다음 하 표를 선택 하고 같은 길이 가 n 인 문자열 을 선택 하여 str 의 끝(실제 비교 할 때)까지 비교 합 니 다.아래 표 시 는 n-m 로 이동 합 니 다.이러한 시간 복잡 도 는 O(n*m)이다.
KMP 알고리즘:복잡 도 O(m+n)구현 가능
왜 시간의 복잡 도 를 간소화 합 니까?
대상 문자열 ptr 의 성질 을 충분히 이용 하 였 습 니 다(예 를 들 어 내부 문자열 의 중복 성 은 중복 필드 가 존재 하지 않 더 라 도 비교 할 때 최대 이 동량 을 실현 합 니 다).
위의 이치 가 이해 되 든 안 되 든 상 관 없 이 내 가 말 한 것 도 사실 안의 내부 원인 을 깊이 분석 하지 않 았 다.
대상 문자열 ptr 고찰:
ababaca
여기 서 우 리 는 길이 가 m 인 전이 함수 next 를 계산 해 야 한다.
next 배열 의 의 미 는 고정 문자열 의 최 장 접두사 와 최 장 접두사 가 같은 길이 입 니 다.
예 를 들 어 abc jkdabc,그러면 이 배열 의 최 장 접 두 사 는 최 장 접두사 와 같 으 면 반드시 abc 입 니 다.
cbcbc,최 장 접 두 사 는 최 장 접미사 와 같 습 니 다.cbc 입 니 다.
abcbc,최 장 접 두 사 는 최 장 접두사 와 같 지 않 습 니 다.
**최 장 접두사 주의:첫 번 째 문자 로 시작 하지만 마지막 문 자 는 포함 되 지 않 습 니 다.
예 를 들 어 aaaa 와 같은 최 장 접두사 와 최 장 접 두 사 는 aaa 입 니 다.**
대상 문자열 ptr,ababaca,길 이 는 7 이기 때문에 next[0],next[1],next[2],next[3],next[4],next[5],next[6]는 각각 계산 한 것 이다.
a,ab,aba,abab,ababa,ababac,ababaca 의 같은 최 장 접두사 와 최 장 접두사 의 길이.a,ab,aba,abab,ababa,ababac,ababaca 의 똑 같은 최 장 접두사 와 최 장 접 두 사 는",",",",",","ab","aba",",",","a"이기 때문에 next 배열 의 값 은[-1,-1,0,1,2,-1,0]이다.여기-1 은 존재 하지 않 음 을 나타 내 고 0 은 존재 길이 가 1,2 는 존재 길이 가 3 임 을 나타 낸다.코드 와 대응 하기 위해 서다.
아래 그림 의 1,2,3,4 는 같다.1-2 사이 의 것 과 3-4 사이 의 것 도 똑 같 습 니 다.우 리 는 A 와 B 가 다르다 는 것 을 발 견 했 습 니 다.이전의 알고리즘 은 내 가 아래 의 문자열 을 앞으로 이동 시 켜 거 리 를 다시 처음부터 비교 하 는 것 이 었 다.그러면 반드시 많은 중복 비교 가 존재 할 것 이다.현재 의 방법 은 내 가 아래 의 문자열 을 앞으로 이동 시 켜 3 과 2 쌍 을 C 와 A 가 같은 지 직접 비교 하 는 것 이다.


코드 분석

void cal_next(char *str, int *next, int len)
{
  next[0] = -1;//next[0]    -1，-1                 
  int k = -1;//k    -1
  for (int q = 1; q <= len-1; q++)
  {
    while (k > -1 && str[k + 1] != str[q])//       ，  k   next[k]，  next[k]   k ，  k    。
    {
      k = next[k];//    
    }
    if (str[k + 1] == str[q])//    ，k++
    {
      k = k + 1;
    }
    next[q] = k;//      k  （               ）  next[q]
  }
}

KMP
이것 은 next 와 비슷 합 니 다.구체 적 으로 코드 를 보 세 요.사실은 위 에서 전체 일치 과정 을 대충 말 했 습 니 다.

int KMP(char *str, int slen, char *ptr, int plen)
{
  int *next = new int[plen];
  cal_next(ptr, next, plen);//  next  
  int k = -1;
  for (int i = 0; i < slen; i++)
  {
    while (k >-1&& ptr[k + 1] != str[i])//ptr str   ， k>-1（  ptr str     ）
      k = next[k];//    
    if (ptr[k + 1] == str[i])
      k = k + 1;
    if (k == plen-1)//  k   ptr    
    {
      //cout << "   " << i-plen+1<< endl;
      //k = -1;//     ，     
      //i = i - plen + 1;//i      ，  for  i++        （                   ），           。
      return i-plen+1;//       
    }
  }
  return -1; 
}

테스트

  char *str = "bacbababadababacambabacaddababacasdsd";
  char *ptr = "ababaca";
  int a = KMP(str, 36, ptr, 7);
  return 0;

str 에 ptr 와 일치 하 는 문자열 이 여러 개 있 으 면 모든 요 구 를 만족 시 키 는 아래 표 시 된 위 치 를 구 하려 면 KMP 알고리즘 을 약간 수정 해 야 합 니 다.위 에 주석 이 떨 어 진 코드 를 보십시오.
복잡 도 분석
next 함수 계산 복잡 도 는(m)로 처음에는 O(m^2)인 줄 알 았 는데 나중에 곰 곰 이 생각해 보 니 calnext 의 while 순환,그리고 외층 for 순환,평균 노점 사상 을 이용 하여 사실은 O(m)입 니 다.이것 은 나중에 생각해 서 쓰 겠 습 니 다.
...........................................................................
사실 본 고 는 이미 끝 났 고 뒤의 것 은 평론 속 의 의문 에 대해 나 는 해답 을 시도 해 보 았 다.
추가 설명(2018-3-14)
댓 글 을 봤 는데 다 들 칼next(..)함수 와 KMP()함수 의

while (k > -1 && str[k + 1] != str[q])
    {
      k = next[k];
    }

화해시키다

while (k >-1&& ptr[k + 1] != str[i])
      k = next[k];

이 while 순환 과 k=next[k]의 심 스 럽 습 니 다!
확실히 말 이 야.나 는 이 몇 줄 의 코드 를 보기 시 작 했 는데,상당히 어 리 석 었 다.이것 은 무엇 을 썼 니?왜 이렇게 썼 니?나중에 비행기 에 올 라 뛰 어 보 니 왜 이렇게 썼 는 지 천천히 알 게 되 었 다.이 몇 줄 의 코드 는 KMP 알고리즘 의 본질 에 대해 잘 알 아야 생각 할 수 있다 고 할 수 있다.대단 해!
직접 보기 calnext(..)함수:
우선 우 리 는 첫 번 째 while 순환 을 보 았 다.그것 이 도대체 무엇 을 했 는 지.
그 전에 우 리 는 먼저 원래 의 절차 로 돌아 갔다.원래 프로그램 에 큰 for()순환 이 있 는데 이 for()순환 은 무엇 입 니까?
이 for 순환 은 next[0],next[1],next[q]의 값 을 계산 하 는 것 입 니 다.
안에 있 는 마지막 문장 next[q]=k 는 순환 이 끝 날 때마다 ptr 의 앞(q+1)글자 로 구 성 된 하위 문자열 의'같은 최 장 접두사 와 최 장 접두사 의 길이'를 계산 한 것 입 니 다.(이 말 은 앞에서 설명 했다!)이'길이'가 바로 k 입 니 다.
자,여기까지 입 니 다.순환 이 q 회 까지 진행 되 었 다 고 가정 합 니 다.즉,next[q]를 계 산 했 습 니 다.우 리 는 next[q+1]를 어떻게 계산 합 니까?
예 를 들 어 ababab,q=4 를 알 았 을 때 next[4]=2(k=2 는 이 문자열 의 앞 5 글자 로 구 성 된 하위 문자열 ababa 에 같은 최 장 접두사 와 최 장 접두사 의 길이 가 3 이라는 것 을 나타 내기 때문에 k=2,next[4]=2.이 결 과 는 우리 가 관찰 하고 계산 한 것 으로 이해 할 수 있 고 프로그램 이 스스로 계산 한 것 으로 이해 할 수 있다.이것 은 중점 이 아니다.중점 은 프로그램 이 현재 의 결과 에 따라 next[5]를 어떻게 계산 하 느 냐 하 는 것 이다.그러면 문자열 ababab 에 대해 우리 가 next[5]를 계산 할 때 이때 q=5,k=2(이전 순환 이 끝 난 후의 결과).그러면 우리 가 비교 해 야 할 것 은 str[k+1]과 str[q]가 같은 지,사실은 str[1]과 str[5]가 같은 지!왜 k+1 에서 비교 합 니까?지난번 순환 에서 우 리 는 str[k]와 str[q](이 q 가 지난번 순환 의 q 임 을 주의 하 세 요)가 똑 같 기 때문에 이번 순환 까지 str[k+1]과 str[q]가 똑 같은 지 직접 비교 합 니 다(이 q 는 이번 순환 의 q 입 니 다).
같 으 면 while()를 뛰 어 내 려 if(),k=k+1 에 들 어가 고 next[q]=k 를 이 어 갑 니 다.즉,ababab 에 대해 우 리 는 next[5]=3 을 얻 을 수 있 습 니 다.이것 은 프로그램 이 스스로 계산 한 것 이 고 우리 가 관찰 한 것 과 같다.
만약 기다 리 지 않 는 다 면,우 리 는'ababac'로 이런 상황 을 묘사 할 수 있다.기다 리 지 않 고 while()에 들 어가 k=next[k]를 진행 합 니 다.이 말 은 str[k+1]에서!=str[q]의 경우,우 리 는 앞으로 k 를 찾 아서 str[k+1]=str[q]를 앞으로 하나씩 찾 을 까요,아니면 더 빠 른 방법 이 있 을까요?한 사람 이 찾 으 면 반드시 된다.즉,너 는 k=next[k]를 k--로 바 꾸 어도 충분히 실행 할 수 있다.그러나 프로그램 은 k=next[k]를 더 빨리 찾 는 방법 을 제시 했다.프로그램 은 일단 str[k+1]!=str[q],즉 접미사 에서 찾 을 수 없습니다.저 는 중간 부분 을 직접 뛰 어 넘 고 접두사 에서 찾 을 수 있 습 니 다.next[k]는 똑 같은 최 장 접두사 와 최 장 접두사 의 길이 입 니 다.그래서 k=next[k]는'k=next[2],즉 k=0'이 된다.이때 str[0+1]과 str[5]가 같은 지,다른 지 비교 하면 k=next[0]=-1.순환 을 벗어나다.
(이 해석 을 알 수 있 을 까?)
이상 은 이 칼next()함수 의

while (k > -1 && str[k + 1] != str[q])
    {
      k = next[k];
    }

가장 이해 하기 어 려 운 점 중 하 나 는 내 가 이해 하 는 것 이 잘못 되 었 다 는 환영 지적 이다.
복잡 도 분석:
KMP 복잡 도 를 분석 하면 KMP 함 수 를 직접 봅 니 다.

int KMP(char *str, int slen, char *ptr, int plen)
{
  int *next = new int[plen];
  cal_next(ptr, next, plen);//  next  
  int k = -1;
  for (int i = 0; i < slen; i++)
  {
    while (k >-1&& ptr[k + 1] != str[i])//ptr str   ， k>-1（  ptr str     ）
      k = next[k];//    
    if (ptr[k + 1] == str[i])
      k = k + 1;
    if (k == plen-1)//  k   ptr    
    {
      //cout << "   " << i-plen+1<< endl;
      //k = -1;//     ，     
      //i = i - plen + 1;//i      ，  for  i++        （                   ），           。
      return i-plen+1;//       
    }
  }
  return -1; 
}

이 물건 은 정말 설명 하기 어렵다.간단하게 말 해 보 자.
코드 로 복잡 도 를 설명 하 는 것 은 비교적 어 려 운 일이 다.

이 그림 은 설명 한다.
일치 하 는 문자열 이 앞으로 이동 할 때마다 큰 단락 으로 이동 하 는 것 을 볼 수 있 습 니 다.일치 하 는 문자열 에 중복 되 는 접두사 와 접두사 가 존재 하지 않 는 다 고 가정 하면 next 의 값 은-1 입 니 다.그러면 매번 이동 할 때마다 일치 하 는 문자열 이 앞으로 m 거 리 를 이동 하 는 것 입 니 다.그 다음 에 다시 한 번 비교 하면 m 회 를 비교 하고'm 거 리 를 이동 하고 m 회 를 비교 하 며 끝까지 이동 하 는 것 이 바로 n 회,O(n)의 복잡 도 를 비교 하 는 것 이다.일치 하 는 문자열 에 중복 되 는 접두사 와 접두사 가 존재 한다 고 가정 하면 우리 가 이동 하 는 거 리 는 상대 적 으로 작 지만 비교 하 는 횟수 도 적 고 전체적인 대가 도 O(n)이다.
그래서 복잡 도 는 선형 복잡 도이 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.