字符串搜索问题

字符串搜索问题之前没有好好想，正常使用自带API或者正值表达式，或者第一反应就是常规的暴力搜索。其实这里面有很多很好玩的算法。Robin-Karp算法比较容易理解，而利用有限自动机进行匹配就开始晕了，最后的KMP算法代码不多，但是计算前缀的方法真是很神奇，静下心想了好久才开窍。神奇！神奇！很神奇。

本文讲一个很神奇的搜索字符串中以某一位开始的最长回文的算法。问题可以简化为从字符串首位开始的最长回文。

问题分析：

public String getLonggestLeftPalindrome(String s){
    int j = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == s.charAt(j)) { j += 1; }
    }
    if (j == s.length()) { return s; }
    return getLonggestLeftPalindrome(s.substring(0, j));
}

改写为非递归方式：

    public String getLonggestLeftPalindrome(String s) {
        if(s==null || s.length()==0) return s;
        
        int len=s.length();
        int j=0;
        while(true){
            for(int i=len-1;i>=0;i--){
                if(s.charAt(i)==s.charAt(j)){
                    j++;
                }
            }
            if(j==len)break;
            len=j;
            j=0;
        }
        return s.substring(0,j);
    }

上面的j是当前累计的字符长度。举几个例子看看。

这里发现只要用很少的迭代次数就可以完成搜索，那需要多少轮呢？

再做几个实验看看：

发现规律大体是以开头字符为开始的最长回文设为palindrome X, S字符串中除了palindrome之后的后缀字符suffix中能发现N个不重叠的palindrome X；然后这个后缀再移除这N个不重叠的palindrome X后分成的两段:前段B和后段E，前段B若不为空则计数1次，(B为空则B=0否则B=1),后段E中如果存在palindrome X中的任意字符则累计一次(E=1, 否则E=0)。所以次数为N+B+E+1(1为回文本身一次）<= N＋2 ＋ 1<=N+3。

以S='abbaxaxbxbxaxaxbxbxaxaxbxbxaxaxbxbxa'为例，palindrome x = 'abba', suffix='xaxbxbxaxaxbxbxaxaxbxbxaxaxbxbxa', suffix中有4个不重叠的abba。suffix除去这个四个不重叠的abba只剩下前段B='x', 所以B=1; 后段E为空所以E＝0；所以需要(4+1+0+1=6次）迭代。

这个规律正确吗？再看S='axcaaaaaaaaaaaaaaa...a', 如果上面的规律正确的话那上面就是最坏的情况。后段中有N个a,字符串S总长为N+2;其需要N＋2次迭代，第i次迭代需要扫描N-i＋1个字符。但事实是只要3次!!!这里发现palindrome后面紧跟着的那个字符x又那么神奇地拯救了算法！！！

那最终规律应该是什么呢？最差情况是什么呢？如何解释每次的j呢？