Manacher 알고리즘, KMP 알고리즘

1. Manancher 알고리즘
Manacher 알고리즘 은 하위 문자열 의 회 문 을 찾 는 데 사 용 됩 니 다. 알고리즘 이 유지 하 는 세 가지 변 수 는 매우 중요 합 니 다. pArr (아래 표 시 된 위치 문자 의 회 문 길이), index (회 문 중심), pR (회 문 반경) 은 다른 알고리즘 보다 효율 이 높 은 이 유 는 앞에서 계산 한 회 문 을 이용 하여 회 문 을 계산 해 야 하 는 지 여 부 를 판단 할 수 있 기 때 문 입 니 다.알고리즘 은 문자열 의 모든 문자 사이 에 특수 문 자 를 삽입 하 였 습 니 다.
알고리즘 코드:

    public char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length]; //            
        int index = -1; //    
        int pR = -1; //    
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

2. KMP 알고리즘
KMP 알고리즘 은 문자열 일치 문 제 를 해결 하 는 동시에 next 배열 을 이용 하여 앞의 계산 결 과 를 이용 하여 뒤의 계산 에 효율 을 높 인 다. next 숫자 는 KMP 알고리즘 에서 매우 중요 하 다.next 배열 의 정의: 길 이 는 match 문자열 의 길이 와 같 습 니 다.
알고리즘 코드

    public int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int si = 0;
        int mi = 0;
        int[] next = getNextArray(ms); //  next  
        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            } else if (next[mi] == -1) {
                si++;
            } else {
                mi = next[mi];
            }
        }
        return mi == ms.length ? si - mi : -1;
    }


    public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }