C 함수 strstr 의 효율 적 인 실현

C 함수 라 이브 러 리 에 함수 strstr (char *, char *) 가 있 습 니 다. 이 는 원래 문자열 에서 하위 문자열 을 찾 는 것 을 실현 합 니 다. 이러한 하위 문자열 을 찾 으 면 원래 문자열 의 시작 위 치 를 되 돌려 줍 니 다. 이러한 하위 문자열 을 찾 지 못 하면 NULL 로 돌아 갑 니 다.
      그러나 함수 라 이브 러 리 에서 실 현 된 것 은 일반적인 상황 에서 만 찾 는 것 입 니 다. 즉, 최 적 화 를 많이 하지 않 았 고 특수 한 문자열 을 실행 할 때 효율 이 낮 습 니 다. 그래서 많은 면접 에서 이 알고리즘 을 개선 하고 효율 이 높 은 strstr 알고리즘 을 실현 하 라 고 요구 합 니 다. 여기 서 저 는 원 알고리즘 을 몇 군데 바 꾸 었 습 니 다. 일부 특수 테스트 사례 에 대해 서 는...실행 효율 은 확실히 원 알고리즘 보다 훨씬 높 습 니 다. 여기에 실현 코드 를 붙 이 고 변경 하 는 부분 은 실현 과정 에서 주석 이 있 습 니 다. 물론 여러분 들 은 더욱 효율 적 인 실현 방법 이 있 습 니 다. 당신 의 지 도 를 아 끼 지 마 십시오.
코드 는 다음 과 같다.
#include <cstring>
#include <iostream>
#include <cassert>

using namespace std;

char* my_strstr(char* str, char* sub)
{
	assert(str != NULL);
	assert(sub != NULL);

	int str_len = strlen(str);
	int sub_len = strlen(sub);

	if (str_len < sub_len)					/*    ,    */
	{
		return NULL;
	}

	if (str_len != 0 && sub_len == 0)		/*aaaaaaaaaaaaaaaaaa, "" ,          */
	{
		cout << "    。。。" << endl;

		return NULL;
	}

	if (str_len == 0 && sub_len == 0)		/*         */
	{
		cout << "         !" << endl;

		return str;
	}

	for (int i = 0; i != strlen(str); ++i)
	{
		int m = 0, n = i;

		cout << "        : " << strlen(str + i) << endl;
		cout << "      : " << sub_len << endl;

		if (strlen(str + i) < sub_len)				/*            ,     */
		{
			cout << "     。。。" << endl;

			return NULL;
		}

		if (str[n] == sub[m])
		{
			while (str[n++] == sub[m++])
			{
				if (sub[m] == '\0')
				{
					return str + i;
				}
			}
		}
	}

	return NULL;
}

좋은 웹페이지 즐겨찾기