�ݺ�ߣ

By�� TheLlama TopCoder Member

◆ The "Naive" Method ◆ Rabin-Karp Algorithms ( 라빈 - 카프 ) ◆ Knuth-Morris-Pratt Algorithms ( 크누즈 - 모리스 - 프랫 )

text[] O(nm) pattern [] A B A B C A A B C C A B C A B C A B C A B C A B C A B C A B C A B C

< 라빈 - 카프 알고리즘 > 문자열에 해당하는 해쉬값이 하나만 존재한다면 , 해쉬값이 같은 두 문자열은 일치한다 !! 특정 값을 나타내는 n 진법의 수가 하나만 존재하는 것과 유사하다 ex) 40 (10) = 101000 (2) = 50 (8) = 2F (16)

Case : 패턴의 길이가 3 일 경우 해쉬값 H 0 = H s[0]..s[2] = s[0] * B 2 + s[1] * B + s[2] H 1 = H s[1]..s[3] = s[1] * B 2 + s[2] * B + s[3] H 2 = H s[2]..s[4] = s[2] * B 2 + s[3] * B + s[4] H 3 = H s[3]..s[5] = s[3] * B 2 + s[4] * B + s[5] ：： S: 문자열 H: 해쉬값 m: 패턴의 길이 B: B >= 문자열에 사용된 문자의 수

초기값 H 0 = H s[0]…s[m-1] = = s[0]*B m-1 + s[1]*B m-2 + …… …… + s[m-2]*B + s[m-1] 점화관계식 H n = H s[n]..s[n+m-1] =(H n-1 - s[n-1]*B m-1 ) * B + s[n+m-1] S: 문자열 H: 해쉬값 m: 패턴의 길이 B: B >= 문자열에 사용된 문자의 수

// a 가 음수일 경우에도 나머지를 구하기 위한 함수 int_mod ( int a , int b ) { return ( a % b + b ) % b ; } function Rabin_Karp ( text [], pattern []) { // n: 문자열 길이 m: 패턴 길이 B: 진법의 수 // M: 열라 큰 소수 ( 오버플로방지 ) if ( n < m ) return ; // 패턴의 길이가 더 길다 당연히 불일치 // 패턴의 해쉬값을 구함 , hp = 0; for ( i = 0; i < m ; i ++) hp = int_mod ( hp * B + pattern [ i ], M ); // 문자열에서 길이 m 만큼의 해쉬값을 구함 , ht = 0; for ( i = 0; i < m ; i ++) ht = int_mod ( ht * B + text [ i ], M ); 다음 페이지로 이어짐…

if ( ht == hp ) // 텍스트의 시작이 패턴과 일치하는지 확인 // 문자열을 따라가면서 해쉬값을 구하고 비교를 반복 // E = ( B m-1 )%M for ( i = m ; i < n ; i ++) { ht = int_mod ( ht - int_mod ( text [ i - m ] * E , M ), M ); ht = int_mod ( ht * B , M ); ht = int_mod ( ht + text [ i ], M ); if ( ht == hp ) // 해쉬값이 일치하면 동일한 문자열 } } 이전 페이지에 이어서…

text[] pattern [] 문자수 :3 A B A B C A A B C C A B C

text[] ht O( n ) A B A B C A A B C C 3 10 4 15 18 1 4 11 X X

< 크누즈 - 모리스 - 프랫 > 찾고자 하는 패턴을 모양을 분석하여 문자열을 불필요하게 비교하는 것을 줄여서 검색시간을 단축한다 . 문자열 검사에서 실패했을 경우 맨 처음으로 돌아가는 것이 아니라 다음 위치로 이동하여 검사를 계속한다

pattern [] 자신자신을 제외한 문자열에서 앞뒤가 같으면서 가장 긴 문자열을 확인 A B C D A B D

pattern [] STATE0 ε STATE2 AB STATE1 A STATE3 ABC STATE4 ABCD STATE6 ABCDAB STATE5 ABCDA A A B B D D C 실패 실패 ※ 나머지는 실패시 STATE0 으로 감 !! A B C D A B D STATE7 ABCDABD

// F[] 는 failure function 으로 불리며 돌아가야 할 위치를 저장함 function build_failure_function ( pattern []) { // m: 패턴의 길이 F[0] = F[1] = 0; // 항상 성립함 for ( i = 2; i <= m ; i ++) { j = F[ i - 1]; // j:i-1 의 가장 긴 앞뒤부분 문자열 길이 for ( ; ; ) { if ( pattern [ j ] == pattern [ i -1]) {F[ i ] = j + 1; break ;} // pattern[j] 는 앞부분의 문자열 뒤의 새로운 문자 // pattern[i-1] 는 뒷부분의 문자열 뒤의 새로운 문자 if ( j == 0) { F[ i ] = 0; break ; } // 문자가 다르면서 j=0 이면 재고의 여지없이 0 j = F[ j ]; // 다르지만 j!=0, 다음으로 긴 앞뒤문자열 재검 } }

text[] ...... ...... Worst Case : O( nm ) Best Case : O(m+n) A B C A B C D A B A B C D A B C D A B D E A B C D A B D A B C D A B D A B C D A B D A B C D A B D A B C D A B D

�ݺ�ߣ

String Searching Algorithms

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to String Searching Algorithms (13)

More from skku_npc (13)

String Searching Algorithms