검색하면, 문자열비교함수 strcmp() 같은걸 떠올려서 O(m*n) 수준의 알고리즘을 사용하는게 딱 내 수준인데,
세상엔 이런 알고리즘들을 즐비하게 만들어내주신다. 저런 패턴을 찾아낸다는것 자체가 신비롭다.
나같은 범인들은 그냥 잘차려진 밥상에 숟갈 얹어 잘 먹어주기만 하면 되는데,
요즘처럼 호기심 왕성한 시기에는 하나하나 파헤쳐본다. 창조자의 기막힌 발상 자체에 경의를 표하며...
아래소스코드는 개략적인 아이디어를 확인하는 샘플코드. 의사코드로 된 것이 좀 더 정확하지만,
내 눈깔은 다른 언어보다 역시나 C/C++ 스타일에 너무 익숙하다. 때론 일상적인 언어보다 나을때가 있다.
--------------------------------------------------------------------------------
/*
* KMP algorithm
* KMP(char *s, char *p)
* find string p in string s
* if find p in s, return index of s
* else return -1
* set N (max string length)
*/
#include <cstdio>
#include <cstring>
#define N 100
using namespace std;
void make_f(char *p, int *f)
{
int pl;
int q, k;
pl = strlen(p);
f[0] = -1;
k = -1;
for( q=1; q<pl; ++q)
{
while( k>=0 && p[k+1] != p[q] ) k = f[k];
if(p[k+1] == p[q]) k++;
f[q] = k;
}
}
int KMP(char *s, char *p)
{
int f[ N ];
int sl, pl;
int i, q;
pl = strlen(p);
sl = strlen(s);
make_f(p, f);
q = -1;
for( i=0; i<sl; ++i)
{
while( q >= 0 && p[q+1] != s[i] ) q = f[q];
if(p[q+1] == s[i]) q++;
if(q == pl-1) return i-pl+1;
}
return -1;
}
'$ SaVvY > » computer' 카테고리의 다른 글
| Pyhon 2.7.3 with Xcode 4 (0) | 2013.07.10 |
|---|---|
| C++의 string 클래스 대신 String 클래스를 만들어 쓰기전에... (0) | 2013.07.10 |
| Building ACE framework on Mac OS X Mountain Lion. (0) | 2013.07.10 |
| Public DNS server (0) | 2013.07.10 |
| Red-Black Tree flow diagram (0) | 2013.07.09 |
