最长前后缀

题目

实现函数：输入一个长度为n的字符串，输出长度为n的数组，其中第i位表示从0到i的子串的最长前后缀长度。例如abaab的最长前后缀长度为2.

解决

1. 暴力法
   对于长度为m的子串，看长度为m-1的前缀、后缀是否相同，相同则返回，否则再看m-2，依次类推
   时间复杂度为O(n)。代码略

2. 更高效的方法
   观察到这样一个事实：
   当output[i]=len时，计算output[i+1]：
   若input[i+1]==input[len]，即考察的前后缀长度加1后仍然相等，则output[i+1]=len+1
   否则，若len>0，则令len=output[len-1]，再继续考察input[i+1]与input[len]；若len=0，则output[i+1]=0。原因如下图所示：

   
   

代码

public static int[] getLPS(String str) {
        int[] result = new int[str.length()];
        int i=1;
        int len = 0;
        while(i<str.length()){
            if (str.charAt(i) == str.charAt(len)){
                len ++;
                result[i] = len;
                i ++;
            }
            else if(len>0){
                len = result[len-1];    //尝试第二长的前后缀，看是否能继续
            }
            else
                i ++; //没有更小的候选答案了，则为0
        }
        return result;
    }

应用：字符串匹配（KMP）

题目

实现KMP匹配算法，空串可以匹配任意字符串，失配则返回-1

代码

public static int strStr(String str, String pattern){
        int m = str.length();
        int n = pattern.length();
        if (n==0)
            return 0;
        int[] lps = getLPS(str);
        int i = 0;
        int j = 0;
        while(i<m){
            if (str.charAt(i) == pattern.charAt(j)){
                i ++;
                j ++;
                if (j==n)
                    return i-n;
            }
            else if (i>0)
                j = lps[j-1];
            else
                i ++;
        }
        return -1;
    }

解释

另一种方法是求next数组，具体方法为next[0]=0或-1，next的其余元素为最长前后缀长度加1.例如模式串“aaba”的next数组为{0，2，1，2}
两种方法的区别在于：
首先next（或lps）数组的计算方式不同
使用next数组进行匹配时，若在第j位失配，则令j=next[j]
而上述方法则是令j=lps[j-1]