Special palindromes

You are given a string $S$ consisting of lowercase Latin letters. You have to select a substring say $S_1$ and prefix say $S_2$ from $S$ of equal length.

Your task is to concatenate them such that one of them is appended in reverse order and form a string $P$ that is either:

• $P=S_1+\text{reverse}(S_2)$ or $S_2+\text{reverse}(S_1)$, here $+$ operator denotes concatenation

 If string $P$ is a palindrome, then it is said to be a special palindrome.

Find the number of strings $S_1$ such that there exists a prefix $S_2$ using which a special palindrome string can be formed.

Example:

Input:  n=5, str="abcde"
Output: 5

Approach

Java

public class SpecialPalindromes {

    public static void main(String[] args)  {
        int n = 5;
        String str = "abcde";
        char[] s = str.toCharArray();
        int[] lps = KMP(s);
        long cnt[] = new long[n];
        for (int i = 0; i < n; ++i) {
            ++cnt[lps[i]];
        }
        long ans = 0;
        for (int i = n - 1; i > 0; --i) {
            cnt[lps[i - 1]] += cnt[i];
            ans += cnt[i];
        }
        System.out.println(n + ans);
    }

    static int[] KMP(char[] t) {
        int m = t.length;
        int lps[] = new int[m];
        int i = 1;
        int l = 0;
        while (i < m) {
            if (t[i] == t[l]) {
                ++l;
                lps[i] = l;
                ++i;
            } else if (l > 0) {
                l = lps[l - 1];
            } else {
                ++i;
            }
        }
        return lps;
    }

}