naiveMatch

소박법에 따르는 캐릭터 라인 조합

함수명

naiveMatch  소박법에 따르는 캐릭터 라인 조합

형식

char *naiveMatch(char *text, int len, char *pattern, int patlen);

인수

text     (입력) 텍스트
len      (입력) 텍스트의 길이
pattern  (입력) 조합 패턴
patlen   (입력) 조합 패턴의 길이

함수치

조합 패턴이 텍스트로부터 발견되었을 경우는 그 포인터,
발견되지 않았던 경우는 0 (NULL).

주의 사항

용례(naiveMatch-test.c )

프로그램(naiveMatch.c )

char *naiveMatch(char *text, int len, char *pattern, int patlen)
{
    char c;
    char *tp, *pp;
    char *textEnd, *patEnd;

    if (patlen == 0)  return text;
    if (len < patlen) return NULL;

    textEnd = text + len - patlen + 1;
    patEnd  = pattern + patlen;

    c = *pattern++;
    while (text ! = textEnd) {
        if (*text++ == c) {
            tp = text;
            pp = pattern;
            do if (pp == patEnd) return text - 1;
            while (*tp++ == *pp++);
        }
    }

    return NULL;
}

설명

캐릭터 라인의 조합은, 캐릭터 라인의 탐색이라고도 한다. 텍스트로 불린다 캐릭터 라인안에, 패턴으로 불리는 캐릭터 라인에 일치하는 부분이 있을까 어때 인지를 조사하는 문제이다. 그러한 부분이 발견되었을 경우에는, 그 장소를 대답한다. 텍스트·에디터에 있어서의 탐색 커멘드나 데이타베이스 에 있어서의 검색 등에 사용되어 사용 빈도가 많은 조작일 것이다.

텍스트에 조합 패턴을 거듭해, 일치할지 어떨지를 조사한다. 일치하는거야 차면 거듭하는 위치를 오른쪽으로 1개않고들 해 반복한다.

이 방법의 계산량은, 최악의 경우 O(mn)이다. 다만, m, n는 각각 텍스트, 조합 패턴의 길이를 나타낸다.