KMP算法next数组活用之前后缀问题

2015/11/17 posted in  算法&数据结构

确切的说这是一篇解题报告(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;
    }
}