Leet Code - 28. Implement strStr()(C++)

예제: Implement strStr()

문제
Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

풀이

자, 문제는 이해하기 매우 쉽다. 문자열 찾기다. 우선 아래 코드를 보자.

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

응..??? 그렇다. 한줄로 끝나버린닷!

하지만 우리는 KMP 알고리즘을 알고있다. KMP 알고리즘을 사용해서 풀어보자.
문자열을 찾는다는 목적에서 string의 find와 같은 역할이다.

KMP 알고리즘은 이전 포스트에서 몇 번 언급했으니 넘어가도록 하자. KMP 알고리즘은 언젠간 다루리..

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	vector<int> setPartialMatch(const string& word) {
		int m = word.size();
		vector<int> pi(m, 0);

		int begin = 1, matched = 0;
		while (begin + matched < m) {
			if (word[begin + matched] == word[matched]) {
				matched++;
				pi[begin + matched - 1] = matched;
			}
			else {
				if (matched == 0) {
					begin++;
				}
				else {
					begin += matched - pi[matched - 1];
					matched = pi[matched - 1];
				}
			}
		}
		return pi;
	}

	int strStr(string haystack, string needle) {
		int n = needle.size();
		if (n == 0) return 0;
		vector<int> pi = setPartialMatch(needle);
		int m = haystack.size();

		int begin = 0, matched = 0;

		while (begin + matched < m) {
			if (haystack[begin + matched] == needle[matched]) {
				matched++;
				if (matched == n) {
					return begin;
				}
			}
			else {
				if (matched == 0) {
					begin++;
				}
				else {
					begin += matched - pi[matched - 1];
					matched = pi[matched - 1];
				}
			}
		}
		return -1;
	}
};

풀이 후기

실제 위 두 알고리즘의 결과는 속도차가 거~의 없다. 메모리 또한 마찬가지.

하지만 입력 string이 매우 커지면 속도차가 많이 날 것이다.
find() 함수는 문자열의 처음부터 끝까지를 검색하지만, KMP 알고리즘은 그보다 훨씬 빨라질 수 있기 때문이다. 예를들어 aaaaaaaaab와 aaaaaab를 비교하는 경우가 그럴 수 있을 것이다.

어쨌든 고급 알고리즘을 익히면 요긴하게 쓰일 곳이 있을 것이다.

참, 그리고 LeetCode 테스트케이스는 매번 돌릴때마다 다른건지, 어쩔때는 속도가 100% 나오지만, 돌릴때마다 다른 결과가 나오기도 한다. 신기하군.

이상으로 포스트를 마친다.