U E D R , A S I H C RSS

Data Structure/String

가장 기본적인 패턴 매칭 알고리즘

~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 여기서 abcab이므로 i = 1이고 i < j 이므로 f(4) = 1

        j = 3 일때, pattern = abca 여기서 abca이므로 i = 0이고 i < j 이므로 f(3) = 0

        같은 것이 없는 경우 - abcabcac f(j) = -1 -- 황재선
        고마워.^^근데 C로 fail() 구현 부분은 더 신기하다. ㅡㅡ; --Leonardong


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.2923 sec