public String longestPalindrome(String string) {
        String s = preprocess(string);
        char[] T = s.toCharArray();
        int n = T.length;
        int[] LPS = new int[n];
        int centerPos = 0, centerRightPos = 0;

        for (int i=1; i<n-1; i++) {
            int i_mirror = 2*centerPos-i;

            LPS[i] = (centerRightPos > i) ? Math.min(centerRightPos - i, LPS[i_mirror]) : 0;

            while(T[i + 1 + LPS[i]] == T[i - 1 - LPS[i]])
                LPS[i]++;

            if (i + LPS[i] > centerRightPos) {
                centerPos = i;
                centerRightPos = i + LPS[i];
            }
        }

        int maxlen = 0;
        int centerIndex = 0;
        for (int i=1; i<n-1; i++) {
            if (LPS[i] > maxlen) {
                maxlen = LPS[i];
                centerIndex = i;
            }
        }

        return string.substring((centerIndex - 1 - maxlen)/2, maxlen);
    }