투폭네

아직 좌우앞뒤위아래 매커니즘이 뇌에 안박혀있어서 굉장히 원시적입니다. 

https://www.acmicpc.net/problem/2178

미로찾기입니다.

bfs를 사용해서 풀려고하였고

아직 탐색이 익숙하지않아서 좀 원시적으로 풀었습니다.

오늘은 KMP알고리즘에대해서 알아보자.

일단 KMP는 사람이름 앞글자를따왔다. 김현복, 민기찬, 박형욱

사실 Knuth–Morris–Pratt Algorithm 이다.

알고리즘때문에 머리만 싸매다보면 정신이 혼미해진다.

우선 저번 문자열에서 공부했듯이, 기본적인 문자열검색에서는 O(N*M) 시간을갖는데, 

이 KMP알고리즘을 쓰면 O(K+N) 이라는 시간이된다.

50 50으로 본다면

기본적인건 2500 이지만 KMP를 쓰면 100으로 줄인다(실제론 100은아님, 아주쬐끔더큼)

일단 공부를하려고 다른블로그나 자료를 찾아보았지만 내 뇌 수준에 맞는 글이없었다. 

그래서 오랜만에 친절한 설명을 곁들여 볼려고 한다.

ABC ABCDAB ABCDABCDABDE
ABCDABD

백준의 문제에서 따왔다. 어차피 다음글에서 풀어볼것이다. 

지금부터 빨간 문자열은 무조건 긴문자열(문자열을찾게되는곳)으로 고정할것이고 파란문자열은 찾을 문자열로 고정할것이다.(보기쉽게) 

위의 문자열에서 아래 문자열을 찾는문제인데, 잘보면 가운데 문자열이 ABCDAB 이다. 어 마지막 D만 일치안하네?

이걸 넣은이유가 무엇일까? KMP로 풀어서 처음에

바로 저 D에 주목하라는것이다. 

기본적인 문자열비교 알고리즘으로 간다면

다음비교는 분명

이런식으로 갈것이다.

하지만 KMP를 이용해서

긴문자열의 가운데인 ABCDAB 를통째로 뛰어넘으라는 문제이다. ( 물론 앞에 ABC도 한번비교후에 뛰어넘음)

그럼 간단하게, 비교 시키위치 저장시킨다음에 만약틀리면 거기서부터 다시 이어서 비교하면 되는거아닌가? 라고 생각할수도있다.

이제 그거에 대해서 태클을 걸려고 다음문자열인 ABCDABCDABDE가 존재한다.

첫비교가 이렇게 된다고 치자.

우리는 c 가 다르기때문에 다음 검색으로 넘어가야한다.

하지만  틀린위치를 저장하고 그다음부터 검색한다면

이런식으로 검색을 시작할것이다.

우리가 원하는 건 노란색 테두리의 문자이고, 

그건 이번검색전에 검색해야됐지만 ,  검색할것을 훌쩍 뛰어넘어버리는것이다.

이것을 방지하기위해 우리는 P[ i ] 배열을 짜야한다. 다른곳에서는( Pi[ ] 배열로 설명을하는데 여긴내블로그니까 내맘대로하꾸여)

P[i]배열을 구하기위해서는 단계가 있는데 

우선 접두사와 접미사를 알아야한다.

접두사와 접미사를 알아야하는 이유는 내가 어떤블로그에서 열심히 읽어도 이해하기가 힘들었으나

끝까지 이해하고나니까 알아야 하는 이유를 알게 되었다.

그러니 일단 따라가보자. 그럼 마지막에는 이유를 찾게 될것이다. 

검색하려는 ABCDABD로 알아보자

접두사: A AB ABC ABCD ABCDA ABCDAB ABCDABD 

접미사: D BD ABD DABD CDABD BCDABD ABCDABD

접두사는 for (int i=0 ;i<length;i++) 느낌이고

접미사는 for(int i=length;i>0;i--) 이런느낌이다. 등호 그런건 중요치않고 이런느낌이라고 느낌적인느낌.

접두사와 접미사가 뭔지는 중요하지않다. 아 접두사는 저렇게 보는거고 접미사는 저렇게 보는거구나 정도만 알면된다.

그럼이제 우리는 P [ i ] 로 돌아가보자.

P [ i ] 는 찾을 문자열의 부분배열과 관련되어있다.

ABCDABD의 부분배열의 갯수는 문자열의 길이와 같다.

아래에 부분배열들을 나타내본다.

이렇게 7개가 된다.

이제여기서 접두사 = 접미사가 같은 것중에 가장 긴놈을 찾는다.

단, 자기자신은 제외해야된다. 위에서봤듯이 접두사(자기자신) = 접미사(자기자신) 가 무조건 성립하게되어버리니까 제외한다.

해보는게 빠르니 해보도록한다.

A => 접두사 A , 접미사 A (자기자신은 위에서 안된다고함) // 총 0개

AB => 접두사 A , 접미사 B (다름)  // 총 0개

ABC => 접두사 A,접미사C (다름)    접두사AB 접미사BC (다름) // 총 0개

ABCD => 접두사 A,접미사D(다름)    접두사AB 접미사CD (다름)    접두사ABC 접미사BCD(다름) // 총 0 개

ABCDA => 접두사A 접미사A (같음!)    접두사AB 접미사DA (다름)    접두사ABC 접미사CDA(다름)    접두사ABCD 접미사BCDA(다름 ) //총 1개

ABCDAB => 접두사A 접미사B(다름)    접두사AB 접미사AB (같음!)    접두사ABC 접미사DAB(다름)    접두사ABCD 접미사CDAB(다름)    접두사ABCDA 접미사BCDAB(다름) // 총 1개

ABCDABD => 접두사A 접미사D(다름)    접두사AB 접미사BD(다름)    접두사ABC 접미사ABD(다름)    접두사ABCD 접미사DABD(다름)    접두사ABCDA 접미사CDABD(다름)    접두사ABCDAB 접미사BCDABD(다름) // 총 0개

다구했다. 물론 본인이 뒤에 개수를써놨지만 개수는 그리 중요하지않다. 

밑줄친곳이 중요한데 접두사와 접미사가 일치하는것중의 최대 길이를 사용한다!.

첫번째 밑줄에서

접두사 A와 접미사A가 같으니 그 길이인 1을 출력한다.( AA라서 2가아니라 A로 같기때문에 1임)

두번째 밑줄에서

접두사 AB와 접미사 AB가 같으니 그 길이인 2를 출력한다. (마찬가지)

그러면 이제 ABCDABD의 P[ i ] 가 나왔는가? P [ 7 ] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 이 된다.

이해가 안간다면 아래 예제들을해본다.

ABAABAB => { 0 , 0 , 1 , 1 , 2 , 3 , 2 } P[2]의 요소가 왜 1인지 P[6]의 요소가 왜 2인지 머리속으로 그려보면, 아 A-A라서 한개 ㅋ AB-AB라서 2네 ㅋ  라는 게 확 와닿을것이다.

AABAA => { 0 , 1 , 0 , 1 , 2 }

AAAAA => { 0 , 1 , 2 , 3 , 4 } 부분문자열부터 생각해야된다는것을 생각하자. 처음부분문자열은 A하나라서 0일수밖에없다, 모든 P[i]의 0번째 원소는 0일수밖에없다 (자기자신포함안되므로) 그래서 잘따라가면 0 1 2 3 4 의 이유를 알 수 있다.

자 우리는 이제 P[ i ] 를 구했다. 

이제 이걸 사용하면 끝. 

우리가 풀려는 문자로 돌아가자.

[나만 돌아가면된다 ]

ABC ABCDAB ABCDABCDABDE
ABCDABD

이런 문자열이 있고 우린 빨간색에서 파란색을 찾을것이다.

그리고 우린 지금까지 P[i]를 구하는연습을했고 여기선

ABCDABD 에 대하여 P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 라는 것 까지 알아냈다.

검사를하자.  

아래부터 말투가 왔다갔다하니조심.

짠 D에서 다르다는걸 찾아냈습니다. D는 짧은것의 4번째 원소입니다. 그러니  저희는 P의 3번째 원소를 확인해줍니다.(3번째까지 맞았으니)

따라서 , P[2]을 확인합시다. ( i는 0부터 시작해서 0 1 2 , 2가 세번째에있는건 아시져?)

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 

p[2]은 0이다. 따라서 접두와 접미가 같은게 없다는 말. 주의할게없다~ 바로 다음으로 넘어간다..

Index 3에서 틀렸고 Index2까지 일치했습니다, p[2]의 값이 0 이었으므로 틀린곳(index 3)부터 이어서 시작해줍니다. (접두와 접미가 같은게 없으니 주의할필요가없음.)

계속 비교를해봅시다

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 

처음부터 달라버리네요 바로 다음으로 밀어줍니다

계속 비교합시다

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 

틀린부분이 나왔습니다 10번째에서.

위에글을 다 읽었으면 아시겠지만 여기는 도중에 접미가 같은 AB가 걸쳐있기때문에 뭔가 있다는걸 인지 하셔야합니다.

짧은문자열의 마지막 알파벳인 D에서 틀렸습니다 즉 7번째 알파벳.

그러니 저희는 그전까지 맞았던 6번째에 집중할필요가있습니다.

P의 6번째 원소인 P[5] = 2 입니다 .따라서 저희는 이녀석의 접두 접미에서 겹치는것중에 제일긴게 2다. "2칸을 조심해야한다" 라는걸 알수있습니다.

따라서 저희는 다음 비교를 index10에서 시작하는것이 아니라 2칸앞인 index8 부터 시작해줍니다 ( 2칸앞이라는걸 p[5] =2 로 알 수 있습니다)

앞에서말햇던 "그건 이번검색전에 검색해야됐지만 ,  검색할것을 훌쩍 뛰어넘어버리는것이다." 라는게 P[i]로 인하여 해결되는 순간입니다.

그러면 다음단계는 아래와 같습니다.

쭉검색을합시다

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 

이제 쉽게 알수있다

3번째에서 틀렸으니까 2번째까지 맞은것이고 P의 두번째원소인 P[1] 을 보면 0 이기때문에 접두접미상관없다 그냥 다땡겨!

그럼 다음비교는 index10부터 시작하게된다.

첨부터 다르다.  넘겨

다른게 나왔다.

P[7] = { 0 , 0 , 0 , 0 , 1 , 2 , 0 } 

틀린건 ABCDABD에서 ABCDAB 즉 6번째까지 맞았기 때문에 P[5] 를 보면 2이므로 길이가 2짜리인 접두접미같은게 있다는것이다.

그래서 2칸을 방지하는겸 , index 17 로 넘어가지말고 2칸앞인 index15를 다음 비교점으로 잡는다.

귀찮으니 생략

그렇게되면 방지할필요없이 그냥 바로 다음인 Index22부터 다시 검색을 시작하면된다.

스크롤양으로봐서는 굉장히 어렵고 복잡하다고 생각할수도있지만, 하다보면 재밌다.

접두접미를 이용해서 처음부터 방지를 해주니까 P 요소만 보고도 얼마나 뛰어넘을지 알수있으니 참편하다.

원리는 완전 깨달았으니 다음에 코드를 짜보도록 하자!

그나저나 말투 통일이 왜이렇게 안돼!!