No older revisions available
No older revisions available
가장 기본적인 패턴 매칭 알고리즘 ¶
~cpp
int nfind(char *strstr,char *ptnptn)
{
int str_len=strlen(str); // 문자열의 길이
int ptn_len=strlen(ptn); // 패턴의 길이
int str_count=0; // 카운터
int ptn_count=0;
while(1)
{
if(strstr[str_count]==ptnptn[ptn_count]) // 문자 비교해서 같을때
{
ptn_count++; // 패턴과 스트링을 가르키는 걸 한개 증가
str_count++;
}
else
{
if(ptn_count==0)
str_count++;
ptn_count=0; // 다를때는 패턴은 0으로
}
if(ptn_count==ptn_len) // 패턴이 문자열 내에 있을때 그 시작 위치 리턴
return str_count-ptn_len+1;
else if(str_count==str_len) // 패턴이 문자열 내에 없을때 거짓(다 돌았는데 카운트가
return -1; // 완성 되지 않았을떄
}
}
- 요건 걍 심심해서 만들어 봤습니다. 뭔가 코드가 좀 더러운거 같긴 하지만..-.-;; 앞으로 공부를 개념을 익히면 소스를 보기 전에 제 손으로 만들어보는 연습을 하려고 합니다.
- Time Complexity는 O(mn) 입니다.(m=문자열의 길이, n=패턴의 길이)
- 이것보다 더 낳은 방법으로 Failure Function을 쓰는 방법이 있져.(O(m+n))
- 요것은 밑에..^^;
- Failure Function 설명 좀 해주실 분? 대체 써 놓은 것을 보아도 개념이 잡히질 않는군요. f(j)값이 어떤 과정을 거쳐서 나오는건가요? -Leonardong
- Failure Function
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| pattern | a | b | c | a | b | c | a | c | a | b |
| f(j) | -1 | -1 | -1 | 0 | 1 | 2 | 3 | -1 | 0 | 1 |
f(j) = largest i such that i < j and 문자열의 0 ~ i번째 = 문자열의 (j - i) ~ j번째, if such an i exists
f(j) = -1(Otherwise)
j = 5 일때, pattern = abcabc 여기서
abcabc이므로 i = 2이고 i < j이므로 f(5) = 2
j = 4 일때, pattern = abcab 여기서
abc
ab이므로 i = 1이고 i < j 이므로 f(4) = 1
j = 3 일때, pattern = abca 여기서
abc
a이므로 i = 0이고 i < j 이므로 f(3) = 0
같은 것이 없는 경우 - abcabcac f(j) = -1 --
황재선
고마워.^^근데 C로 fail() 구현 부분은 더 신기하다. ㅡㅡ; --
Leonardong
