= 가장 기본적인 패턴 매칭 알고리즘 =
{{{~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 여기서 [[HTML(<b><font color=red>)]]abc[[HTML(</font></b>)]][[HTML(<b><font color=blue>)]]abc[[HTML(</font></b>)]]이므로 i = 2이고 i < j이므로 f(5) = 2

     j = 4 일때, pattern = abcab 여기서 [[HTML(<b><font color=red>)]]ab[[HTML(</font></b>)]]c[[HTML(<b><font color=blue>)]]ab[[HTML(</font></b>)]]이므로 i = 1이고 i < j 이므로 f(4) = 1

     j = 3 일때, pattern = abca 여기서 [[HTML(<b><font color=red>)]]a[[HTML(</font></b>)]]bc[[HTML(<b><font color=blue>)]]a[[HTML(</font></b>)]]이므로 i = 0이고 i < j 이므로 f(3) = 0

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

----
DataStructure