문자열 검색 알고리즘 간단히 설명하면 문자열을 검색할 때 앞에서 부터 하는게 아니라 뒤에서 부터 시작하는 알고리즘이다.
비교를 하다가 문자가 다르다는 것을 알았다면, 그 문자가 검색키 문자열에 포함되어 있다면 그 만큼 이동함.
그 문자가 포함되어 있지 않다면 검색키 문자열 길이만큼 점프.
자세한건 아래 참고.
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
간단하게 C언어로 구현해 보았다.
#include <stdio.h>
#define MAXLEN 1000
int mystrlen(char *m)
{
int n = 0;
while (*m != '\0') {
*m++;
n++;
}
return n;
}
bool compareString(char s[], char k[], int idx, int keyLen, int* jumpIdx)
{
int last = keyLen-1;
bool matchFlag = true;
for (int i = (idx + last); i >= 0; i--)
{
//printf("s[%d]=(%c), key[%d]=(%c)\n", i, s[i], last, k[last]);
if (s[i] == k[last])
{
if (last == 0)
{
*jumpIdx = keyLen;
return true;
}
}
else {
for (int j = last-1; j >=0; j--)
{
if (k[j] == s[i])
{
*jumpIdx = keyLen-j-1;
return false;
}
}
*jumpIdx = keyLen;
return false;
}
last--;
}
return false;
}
void main()
{
char source[MAXLEN] = "tomato dog cat radio good";
char key[10] = "cat";
int keyLen = mystrlen(key);
for (int i = 0; source[i] != '\0';)
{
int jump = 0;
//printf("\n==>\n");
//for (int j = 0; j < keyLen && source[i + j] != '\0'; j++)
//{
// printf("%c", source[i + j]);
//}
//printf("\n");
//for (int j = 0; j < keyLen ; j++)
//{
// printf("%c", key[j]);
//}
//printf("\n==<\n");
bool a = compareString(source, key, i, keyLen, &jump);
if (a)
printf("match");
i += jump;
}
printf("n=%d", mystrlen(key));
printf("\n");
}
