[LeetCode][Java] 28. Implement strStr() (문자열, KMP)

굳이 KMP 아니고 브루트포스로 해도 통과가 되는 것 같음

KMP 강의 들으면서 풀어보라고 했던 문제라 그냥 KMP 복습이나함 

 

Line:6 for문의 조건문을 i<ptn.length()로 실수함 -> i<input.length()

이거 알고리즘 풀면서 느끼는건데 ide가 없으면 진짜 안되겠는게

자동완성은 제끼더라도 디버깅하려면 진짜 필수임..

 

class Solution {
    private int KMP(String input, String ptn){
        int[] pi = getPi(ptn);
        
        int j=0;
        for(int i=0; i<input.length(); i++){
            while(j>0 && ptn.charAt(j)!=input.charAt(i))
                j = pi[j-1];
            if(ptn.charAt(j)==input.charAt(i)){
                if(j==ptn.length()-1)
                    return i-(ptn.length()-1);
                else
                    j++;
            }
        }
        return -1;
    }
    
    private int[] getPi(String ptn){
        int[] pi = new int[ptn.length()];
        
        int j=0;
        for(int i=1; i<ptn.length(); i++){
            while(j>0 && ptn.charAt(j)!=ptn.charAt(i))
                j = pi[j-1];
            if(ptn.charAt(j)==ptn.charAt(i)){
                pi[i] = ++j;
            }
            
        }
        return pi;
    }
    
    public int strStr(String haystack, String needle) {
        if(needle.length()==0)
            return 0;
        
        return KMP(haystack, needle);
    }
}