자, 이제부터 카빈-카프 알고리즘을 통한 문자열 탐색 방법을 알아보자.
일단, 문자열 S에서 문자열 P를 찾는다고 가정할 때, 문자열 P의 값 p를 구해놓는다. 그리고나서 문자열 S의 길이를 Slen, P의 길이를 Plen 이라고 할 시, S[i]부터 S[i+Plen-1]까지의 값을 구하는 것이다. 하지만, 이렇게 한다면 원시적인 문자열 탐색 알고리즘을 더 어렵게만 만드는 꼴이다. 이를 더욱 빠르게 만들어보자. S[i]~S[i+Plen-1]의 문자열의 값을 A[i](0<=i<=Slen-Plen)라고 할 시, A[i]의 점화식을 세울 수 있다. (i>=1)
자, 이것으로 기본적인 베이스는 완성되었다. 하지만 우리는 더 유의해야할 것이 있다.
만약, 알파벳으로 이루어진 100자리 수의 값을 구하려 한다면? 아니면, 더 큰 값을 구하려 한다면? 당연히, 저장하지 못하고 뻗어버릴 것이다. 고로 우리는 해결책이 필요하다. 그 해결책은, 큰 소수 q를 구하여, 값을 q의 나머지로 만드는 것이다.
하지만 만약에, q의 나머지가 일치하는 다른 값이 있다면? 그렇다면 잘못된 값을 출력할 수도 있다. 그런 경우에 소수 q를 아무리 크게 잡아봐도 가능성은 항상 존재한다. 고로, 나머지가 같은 것을 체크한 후 문자열이 실제로 일치하는지 다시 체크해야한다. 이제부터 소스를 보자.
(단, 문자열은 알파벳으로만 이루어져있다는 가정 하의 소스이다.) (아직 테스트는 못해봤으므로 틀릴 수도 있다. 후에 수정한 소스를 알려주면 감사하겠다.)
#include <stdio.h>
#include <string.h>
char s[1000]={0},p[100]={0};
int slen,plen,q=113,pkey=0,a[1000]={0},tenp=1;
int main()
{
int i,j;
bool check;
scanf("%s",s);
scanf("%s",p);
slen=strlen(s),plen=strlen(p);
for(i=0;i < plen;i++) pkey*=10,pkey%=q,pkey+=p[i];
for(i=0;i < plen;i++) a[0]*=10,a[0]%=q,a[0]+=s[i];
for(i=1;i < plen;i++) tenp*=10,tenp%=q;
for(i=1;i < slen-plen;i++)
{
a[i]=(a[i-1]-tenp*s[i-1]+q)%q+s[i+plen-1];
if(a[i]==p[i])
{
check=true;
for(j=0;j < plen;j++)
{
if(p[j]!=s[i+j])
{
check=false;
break;
}
}
if(check) printf("Matched : %d to %d",i+1,i+plen);
}
}
return 0;
}