[LeetCode][Java] 796. Rotate String (문자열, KMP)

class Solution {
    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 boolean rotateString(String input, String ptn) {
        if(input.length()!=ptn.length()) 
            return false;
        
        
        int[] pi = getPi(ptn);
        int len = input.length();
        
        int j=0;
        for(int i=0; i<len*2; i++) {
            while(j>0 && ptn.charAt(j) != input.charAt(i%len))
                j = pi[j-1];
            
            if(ptn.charAt(j) == input.charAt(i%len)) {
                if(j == ptn.length()-1) {
                    return true;
                }
                else 
                    j++;
            }
                
        }
        
        return false;
        
    }
}