C Library function strstr함수의 고찰

프로그래밍/C 2008/03/18 22:32

라이브러리 함수로 알아보는 C언어,
strstr함수의 고찰 by 황의범 2008.3.~

먼저 strstr함수를 말로 풀어보자면 , 다음과 같다.

두개의 스트링(0 스트링을 의미함)을 인자로 해서 첫번째 스트링에 두번째 스트링이
있는지 확인하여 스트링이 존재하면 존재하는 위치의 포인터를 결과값으로 넘겨주는
유용한 스트링관련 함수이다.

MAN페이지의 메뉴얼의 필요한 부분만의 번역은 다음과 같다.

strstr - substring을 반환한다.
#include <string.h>  string.h에 정의되어있다.
함수원형
  char *strstr(const char *haystack,const char *needle);
설명
  strstr()함수는 haystack 스트링에서 needle 스트링과 일치하는 첫번째
부분의 위치를 반환한다. '\0' 은 비교하지 않는다.

리턴값
strstr() 함수는 substring이 시작하는 포인터를 반환하거나
substring이 발견되지 않는다면 NULL을 반환한다.

일단 위의 말로푼 설명과 MAN페이지의 용법을 가지고 이 strstr함수를
작성하는 것이 임무라고 치면 어떤 알고리즘을 생각하겠는가?

십수년전에 멀티플랫폼용으로 xbase를 인터페이싱하는 라이브러리를 만들까하다가
처음 프로토타입만 만들고 그만둔적이 있었는데 , 데이타베이스의 빠른 발전과
오픈소스의 발전으로 보아 공개DB를 누구나 쓰게 될것 같아서 였다.
어찌되었든 그때 만든 함수중 하나가 strstr과 비슷한 기능를 하는 특수목적 함수였다.
당연히 strstr과 동일한 기능은 아니다. 같은 기능이라면 strstr를 썼을 것이다.

strstr를 작성한다고 치고 대략의 알고리즘을 생각해보면 다음과 같다.

1. 두번째 스트링의 첫문자를 가지고 , 첫번째 스트링을  검색하여
  일치하는 포인트를 찾는다.
  포인트가 발견되면 2번으로 , 끝까지 발견되지 않으면 0을(NULL) 리턴한다.

2. 그 위치로부터 두번째스트링이 일치하는지 비교한다.
  비교하여 일치하면 결과를 넘겨주고 일치하지 않으면
  검색한 포인트 다음으로 부터 1번을 수행한다.

문제의 난이도가 복잡하지 않은 관계로 그 당시 짧은 생각만으로도 위의
알고리즘을 도출할 수 있었다. 아마 누구든지 생각해보면 쉽사리 얻을수 있는
알고리즘이라 생각된다.  더 좋은 알고리즘이 있을까 더 생각해보았지만
아직 생각해내지 못했다.

그렇다면 strstr는 실제로 위와 같은 알고리즘을 쓸까?
한번 찾아 보았다. 2008년 3월에 공개된 gcc4.3.0 최신버전으로 strstr.c 를 확인 해보았다.
다음과 같다.

#include <stddef.h>

extern char *strchr (const char *, int);
extern int strncmp (const void *, const void *, size_t);
extern size_t strlen (const char *);

char *
strstr (const char *s1, const char *s2)
{
  const char *p = s1;
  const size_t len = strlen (s2);

  for (; (p = strchr (p, *s2)) != 0; p++)
  {
     if (strncmp (p, s2, len) == 0)
       return (char *)p;
  }
  return (0);
}

위에서 strchr 함수는 스트링안에서 주어진 char가 일치하는 첫부분의 포인터를
넘겨주는 함수이며  strncmp 함수는 두개의 스트링을 비교하는 함수이다.

함수내용을 보면  s2 스트링의 첫문자를 가지고(*s2), s1스트링의 첫부분부터 끝부분까지
검색하면서 (for문) 첫문자가 일치하는 부분에서 strncmp를 통하여 비교하고 동일하지
않는 스트링이라면 다시 그부분부터 s2스트링의 첫문자가 일치하는 곳이 있는지
검색하면서 찾는 것이다.

역시 같은 알고리즘이다. 알고리즘이 짧고 명확해서 코드구현을 다양하게 한다고 해도
에셈코드상으로 보면 거의 비슷한 성능을 낼것으로 보이지만  GCC의 구현코드를 보면
얼마나 세심하게 최적의 코드를 섰는지 감탄하게 된다.

strstr은 동종의 비슷한 기능(하나의 스트링 안에서 서브스트링을 찾는)의 함수중에
가장 탁월한 성능을 가지고 있다.

물론 특수한 경우에는 Bayer-Moor 알고리즘이나 , Patricia 알고리즘을 사용하여
원하는 함수를 만들수 있다.

top

Trackback Address :: http://www.xevious7.com/trackback/321

Write a comment