김보안의 블로깅
  • 🏠 Home
  • 📚 Project
    • Blockchain
      • 🎦 PickMe
      • 🎦 IoTC
      • 🎦 Blackchain
      • 📃 Gemology
      • 🎦 PickMe
      • 🎦 PickMe
    • AI
      • 👋 A.I. Dream Reader
      • 🎦 A.I. Dream Reader
    • Security
      • 🎦 SNAC
    • Education
      • 🎦 Smart Lecture
  • 🤸‍♂ Hobby
    • Music
      • Violin
      • Guitar
      • Piano
      • Drum
    • Flower
      • Flower Certificate
    • Sport
      • Ski
      • Skateboard
      • Golf
      • Boxing

2018년 12월 27일 목요일

KMP 쉽게 이해하기 (Failure Function 이해)

 SecureKim     오전 12:39     알고리즘, Failure function, KMP     No comments   



여기서는 KMP 자체보다는 핵심인 Failure function 에 대한 설명만 한다.




F 함수를 재귀로 디게 어렵게 설명한다음 뭐 어려운 것이다


원래 한번에 이해가 안되는게 당연하다고 하는데


혼자 해 보니까 사실 어려운 개념이 아니었다.




F(i) 함수의 정의 :
문자열에서 1 ~ i 까지 항목을 고려했을 때,
접두사와 접미사가 같은 최대의 길이.






즉, ABABA 를 생각해 보자.


F(1) 은 1 항목 (A) 를 고려해 보면 접두사와 접미사가 같은 최대 길이가 0 이다.


F(2) 는 2 항목 (AB) 까지 고려해 보면 A랑 B가 다르니까 0 이다.


F(3) 는 3 항목 (ABA) 까지 고려해 보면 첫 A와 마지막 A 가 같으니까 길이가 1이다.


F(4) 는 4 항목 (ABAB) 까지 고려해 보면 AB와 AB 가 같으니까 길이가 2이다.


F(5) 는 5 항목 (ABABA) 까지 고려해 보면 ABA와 ABA 가 같으니까 길이가 3이다.




그러면 F 함수에 대한 규칙을 찾을 수 있다.


화살표 두개로 시작해서, 일치하기 시작하면


앞쪽 화살표 부분에서는 F 함수에 1씩 더하고,


뒤쪽 화살표는 쫓아가는 모습이라고 생각하면


바~~로 이해되는 부분이다.



↓
↓
 
 
 
A
B
A
B
A
0
0
 
 
 

 

↓
 
↓
 
 
A
B
A
B
A
0
0
1
 
 



 
↓
 
↓
 
A
B
A
B
A
0
0
1
2
 

( 앞쪽 A는 이미 비교해서 맞았기 때문에 다시 비교할 필요가 없다. )




 
 
↓
 
↓
A
B
A
B
A
0
0
1
2
3




그럼 뒤쪽 화살표가 쫓아가다가 틀렸다면 ?


불쌍하게도 뒤쪽은 다시 처음부터 비교 시작이다.


이제 긴 예제를 들어보자


↓
↓
 
 
 
 
 
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
 
 
 
 
 
 
 
 
 
 

 

↓
 
↓
 
 
 
 
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
 
 
 
 
 
 
 
 
 

 

↓
 
 
↓
 
 
 
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
 
 
 
 
 
 
 
 

 

↓
 
 
 
↓
 
 
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
 
 
 
 
 
 
 

 

 
↓
 
 
 
↓
 
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
 
 
 
 
 
 

 

 
 
↓
 
 
 
↓
 
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
 
 
 
 
 

 

 
 
 
↓
 
 
 
↓
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
!
 
 
 
 

 

↓
 
 
 
 
 
 
↓
 
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
 
 
 
 

 


 
↓
 
 
 
 
 
 
↓
 
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
 
 
 

 

 
 
↓
 
 
 
 
 
 
↓
 
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
3
 
 

 

 
 
 
↓
 
 
 
 
 
 
↓
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
3
!
 

 

↓
 
 
 
 
 
 
 
 
 
↓
 
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
3
1
 

 

 
↓
 
 
 
 
 
 
 
 
 
↓
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
3
1
!

 

↓
 
 
 
 
 
 
 
 
 
 
↓
B
A
C
C
B
A
C
B
A
C
B
C
0
0
0
0
1
2
3
1
2
3
1
0

 


아주 개념 이해가 바로 되어 버리지 않았는가?


짝짝짝 !




그리고 코드는 이렇게나 짧다 !


다만, 코드를 이해하는것은 쉽지 않으니


찬찬히 따라가 보자!


void kmp(char *p) {
  int n = strlen(p);
  int i = -1, j = 0;
  int F[MAX_LEN];
  F[0] = -1;
  while (j < n) {
    if (i == -1 || (i >= 0 && p[i] == p[j])) F[++j] = ++i;
    else i = F[i];
  }
}





Read More
  • Share This:  
  •  Facebook
  •  Twitter
  •  Stumble
  •  Digg
최근 게시물 이전 게시물 홈

페이지

  • 홈
  • Hobby

Categories

  • AI
  • android
  • AWS
  • Blockchain
  • Hardware
  • Javascript
  • mysql
  • Node.js
  • Plasma
  • review
  • Security
  • Study
  • Video
  • windows

Popular Posts

  • 블랙보드 강의 녹화 영상 다운로드 가능한 방법 (노설치)
    별도의 설치도 필요 없고 아주 쉽습니다. 구글 크롬브라우저 에서 블랙보드 녹화 영상에  다운로드 가능한 메뉴가 나오게 하는 코드입니다.  먼저 블랙보드 강의자료에 입장하고, 재생 버튼을 클릭 하지 않은 상태로 F12 를 입력합니다. 재생을 클릭하지 마세요.
  • 회사 프록시와 인증서에 고통받는 그대를 위한 글 (Bash, Gradle, Python, wget, nodejs(npm), apt-get, cURL, git, yarn, androidStudio)
    대기업에 입사하면 장단점이 있는데, 단점 중에 하나가 회사에서 프록시를 사용하여 트래픽 감시를 하므로 프록시 설정을 해주어야 한다는 점 입니다. 특히, 회사에서는 https 트래픽도 감시를 하므로 인증서도 설정해 주어야 합니다. 그런데 문...
  • [Node.js] Redis 의 hmset
    Redis 의 hmset 사용하기 var redis = require('redis'); var client=redis.createClient(포트,호스트,null); /* * MySQL을 사용하다가 Redis를 사용해보니 신세...

Blog Archive

  • ►  2023 (1)
    • ►  1월 (1)
  • ►  2022 (10)
    • ►  12월 (1)
    • ►  11월 (3)
    • ►  9월 (1)
    • ►  8월 (1)
    • ►  6월 (2)
    • ►  3월 (2)
  • ►  2021 (9)
    • ►  12월 (3)
    • ►  11월 (1)
    • ►  6월 (1)
    • ►  5월 (2)
    • ►  4월 (2)
  • ►  2020 (12)
    • ►  10월 (1)
    • ►  9월 (2)
    • ►  7월 (1)
    • ►  6월 (1)
    • ►  5월 (5)
    • ►  4월 (1)
    • ►  2월 (1)
  • ►  2019 (14)
    • ►  10월 (2)
    • ►  7월 (1)
    • ►  3월 (4)
    • ►  2월 (2)
    • ►  1월 (5)
  • ▼  2018 (14)
    • ▼  12월 (2)
      • KMP 쉽게 이해하기 (Failure Function 이해)
      • Node.js 에서 for 문 안에 있는 비동기 함수에 대해 동기 맞춰주는 방법
    • ►  11월 (4)
    • ►  10월 (1)
    • ►  8월 (2)
    • ►  5월 (4)
    • ►  1월 (1)
  • ►  2017 (12)
    • ►  10월 (2)
    • ►  9월 (9)
    • ►  5월 (1)
  • ►  2016 (8)
    • ►  10월 (2)
    • ►  8월 (1)
    • ►  6월 (1)
    • ►  1월 (4)
  • ►  2015 (6)
    • ►  12월 (3)
    • ►  10월 (1)
    • ►  6월 (1)
    • ►  5월 (1)
  • ►  2014 (10)
    • ►  11월 (1)
    • ►  9월 (1)
    • ►  7월 (1)
    • ►  6월 (1)
    • ►  5월 (3)
    • ►  4월 (1)
    • ►  3월 (2)
  • ►  2013 (28)
    • ►  12월 (3)
    • ►  11월 (6)
    • ►  10월 (6)
    • ►  9월 (6)
    • ►  8월 (1)
    • ►  7월 (3)
    • ►  6월 (3)

구독

글
Atom
글
전체 댓글
Atom
전체 댓글

로드 중입니다...

각오

직접 해보지 않은 것은 포스팅 하지 않겠습니다.

Copyright © 김보안의 블로깅 | Powered by Blogger
Design by Hardeep Asrani | Blogger Theme by NewBloggerThemes.com | Distributed By Gooyaabi Templates