确切的说这是一篇解题报告（SDUTOJ 2784：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2784）。

前置技能 KMP字符串匹配算法: KMP字符串匹配算法

正如题目中描述：

你的任务是找出一个字串s，s既是String的前缀，又是String的后缀，并且s也出现在String的中间部分（既不是前缀，也不是后缀），s的长度越长越好。

很明显这是一道KMP算法周边题目，说是KMP算法是因为需要计算next数组，说是周边是因为这并不是一道匹配类型的题目。

正如《KMP字符串匹配算法》所说，next数组的目的是保存的匹配过的 S 串中还有多少直接等于 T 串的。但实际上，next中的数值的含义在不同的使用场景还有很多种理解。

比如求前后缀的题目中，我们就可以把next中的数组看做在next[i]（next[i]！=0 and next[i] != -1）出，存在重复的字段String[0,next[i]]。

而对于这个题目，对于长度为len-1的字符串，那么next数组的长度为len。

如果在next数组中，如果next[len]为0，这可以说明不存在后缀和前缀相同的情况。如果next[len]不为0，这说明前缀和后缀相同，但是还不能说明中间存在这一循环体。

如果next[len]不为0，而且存在和next[len]一样的值，也就是说在在字符串中间出现了循环题，也就可以断定存在符合题目要求的字符串，而长度就是next[len]（也就是后缀和前缀共同的长度）。

但如果串是一个循环串，比如像"papapapa"这种，那么next是递增的。因此不能用上段的方式判断十分满足题目要求。

因此需要判断出去最短循环节之后时候还是循环串。而除去最短循环串，便是String[0,next[len]]。因此，在该串的基础上进行判断，也就是判断next[next[i]]十分还是一个有效的值（非0和非-1），如果有效，说明依然存在字段重复。

因此这个题目就非常清楚了：只需要寻找next[i] == next[len]和判断 next[next[len]] != 0 且 next[next[len]] != -1。

把KMP相关算法封装，这个题目的核心代码就变成了：

/**
 * SDUTOJ 2748
 * Created by hypo on 15-11-15.
 */

class TestString{
    private String str;
    private int[] next;

    //初始化 顺便获得next数组
    public TestString(String str) {
        this.str = str;
        next = getNext();
    }

    //获取next数组
    private int[] getNext(){
        char[] chars = this.str.toCharArray();
        int len = chars.length;
        int[] next = new int[len + 1];
        int k = -1, i = 0;
        next[0] = -1;

        while(i < len){
            if(k == -1 || chars[k] == chars[i]){
                i++;
                k++;
                next[i] = k;
            }else{
                k = next[k];
            }
        }
        return next;
    }

    //获得结果 null表示不符合题目要求
    public String getAns(){

        int len = this.str.length();

        if(next[len] == 0){
            return null;
        }

        for(int i = 0;i < len;i++){
            if(this.next[i] == next[len]){
                return this.str.substring(0,next[len]);
            }
        }

        if (next[next[len]] != 0 && next[next[len]] != -1)
        {
            return this.str.substring(0,next[next[len]]);
        }

        return null;
    }
}