[프로그래머스] 111. 부분 문자열

입출력 예

입출력 예 설명

• 본문과 동일합니다.

• "tbbttb"에는 "tbt"가 없으므로 0을 return합니다.

코드

class Solution {
    public int solution(String str1, String str2) {
        int result = 0;

        for (int i = 0; i <= str2.length() - str1.length(); i++) {

            for (int j = 0; j < str1.length(); j++) {
                if (str2.charAt(i + j) != str1.charAt(j)) {
                    result = 0;
                    break;
                } else  {
                    result = 1;
                }

                if(j == str1.length() - 1) {
                    return result;
                }
            }
        }

        return result;
    }
}

KMP 알고리즘

    public int solution(String str1, String str2) {
        // str1의 접두사와 접미사가 겹치는 정보를 미리 계산한다.
        int[] lps = makeLps(str1);

        // textIndex: str2에서 현재 확인 중인 위치
        // patternIndex: str1에서 현재 확인 중인 위치
        int textIndex = 0;
        int patternIndex = 0;

        while (textIndex < str2.length()) {
            // 현재 문자가 같으면 두 문자열의 다음 문자를 비교한다.
            if (str2.charAt(textIndex) == str1.charAt(patternIndex)) {
                textIndex++;
                patternIndex++;

                // str1의 끝까지 모두 일치하면 부분 문자열을 찾은 것이다.
                if (patternIndex == str1.length()) {
                    return 1;
                }
            // 불일치했지만 앞에서 일치한 문자가 있다면,
            // LPS를 이용해 str2의 문자를 다시 비교하지 않고 str1만 이동한다.
            } else if (patternIndex > 0) {
                patternIndex = lps[patternIndex - 1];
            // 아직 일치한 문자가 없다면 str2의 다음 위치부터 다시 비교한다.
            } else {
                textIndex++;
            }
        }

        // str2를 끝까지 확인했지만 str1을 찾지 못한 경우
        return 0;
    }

    private int[] makeLps(String pattern) {
        // lps[i]: pattern[0..i]에서 접두사와 접미사가 같은 최대 길이
        int[] lps = new int[pattern.length()];
        int prefixLength = 0;
        int index = 1;

        while (index < pattern.length()) {
            // 현재 문자가 접두사의 다음 문자와 같으면 겹치는 길이를 늘린다.
            if (pattern.charAt(index) == pattern.charAt(prefixLength)) {
                lps[index] = prefixLength + 1;
                prefixLength++;
                index++;
            // 더 짧은 접두사와 비교하기 위해 이전 LPS 값을 사용한다.
            } else if (prefixLength > 0) {
                prefixLength = lps[prefixLength - 1];
            // 일치하는 접두사가 없으면 해당 위치의 LPS는 0이다.
            } else {
                index++;
            }
        }

        return lps;
    }