strStr

problem

주어진 두개의 스트링에서 두번째 스트링이 첫번째 스트링에 포함되어 있는지 찾고 그 시작점을 찾는 문제입니다.
https://leetcode.com/problems/implement-strstr

solution

class Solution {
    
public:
    int strStr(string haystack, string needle) {
        if(haystack.size() < needle.size()) {return -1;}
        int answer = -1 , size_s = haystack.size() , size_n = needle.size();
        for(int i=0;i<=size_s - size_n;i++)
        {
            answer = i;
            for(int j = 0; j<size_n;j++)
            {
                if(haystack[i+j] != needle[j])
                {
                    answer = -1;
                    break;
                }
            }
            if(answer != -1)
            {
                return answer;
                break;
            }
        }
        return answer;
    }
};

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

중간에 겪은 오류

바로 생각난 풀이는 하나하나 모두 검사하는 브루트 포스 알고리즘을 사용하는 것이었다. 문제를 푼 후 실행 시간이 너무 길었고,

다른 사람들의 풀이를 보니까 KMP, 보이어 무어 알고리즘등이 사용된 것을 알 수 있었다.