(해결 대기) Leetcode 28. Implement strStr () 문제 풀이 보고서 [C 라 이브 러 리 함수 strstrstr () 시 뮬 레이 션 - 문자열 중성자 문자열 이 처음 나타 난 주소]

1679 단어 LeetCodeBeatTheOffer
28. Implement strStr()
 
인터넷 주소 제출 https://leetcode.com/problems/implement-strstr/
Total Accepted: 105435 
Total Submissions: 422883 
Difficulty: Easy
Implement strStr( )  .
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
분석:
AC 코드:
// LeetCode, Implement strStr()
// KMP  ,     O(N+M),     O(M)
class Solution {
	public:
		int strStr(const string& haystack, const string& needle) {
			return kmp(haystack.c_str(), needle.c_str());
		}

	private:
		/*
		* @brief  next .
		**
		@param[in] pattern
		* @param[out] next next
		* @return
		*/
		static void compute_prefix(const char *pattern, int next[]) {
			int i;
			int j = -1;
			const int m = strlen(pattern);
			next[0] = j;
			for (i = 1; i < m; i++) {
				while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
				if (pattern[i] == pattern[j + 1]) j++;
				next[i] = j;
			}
		}
		/*
		* @brief KMP
		**
		@param[in] text    
		* @param[in] pattern    
		* @return -1     ,  -1
		*/
		static int kmp(const char *text, const char *pattern) {
			int i;
			int j = -1;
			const int n = strlen(text);
			const int m = strlen(pattern);
			if (n == 0 && m == 0) return 0; /* , */
			if (m == 0) return 0; /* a, */
			int *next = (int*)malloc(sizeof(int) * m);
			compute_prefix(pattern, next);
			for (i = 0; i < n; i++) {
				while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
				if (text[i] == pattern[j + 1]) j++;
				if (j == m - 1) {
					free(next);
					return i-j;
				}
			}
			free(next);
			return -1;
		}
};

좋은 웹페이지 즐겨찾기