<算法书>最长前缀是逆串的子串

问题描述 ：设T是长为n的文本串。描述一个找出T的最长前缀的O(n)时间的方法，该前缀也是T的逆串的一个子串。 (来自《Algorithm Design》(中文版：算法分析与设计) - Chapter9 - 文本处理 - 创新题C-9.12）

 

分析：既然要在O(n)时间内完成，KMP算法是可以考虑的。根据题目要求我们发现要让T的前缀匹配到T的逆串。那么我们可以把T的逆串作为主串，T作为模式串。对KMP算法做如下修改：

 

(1) 在匹配逻辑中，主串指针 i 从T逆向开始查找，即i=(T.length-1) ——> 0。模式串指针 j 从T正向开始查找，即j=0 ——> (T.length-1)。这样就不用首先做T逆向的处理了。

 

(2) 每一次T[i]==T[j](i 为T的逆序指针，j为T的顺序指针)，都用一个字符串累加起来。直到遇上不相等的时候，则保留原字符串，清空后重新开始累加。直到 i=0为止。此时，所有保留的字符串都是满足条件的T的前缀子串，在比较长度取出最大的字符串即可。

 

Java代码如下：

public class SelfKMP {

	private int[] next=null;
	private char[] mainAry=null;
        //记录匹配上的所有前缀
	ArrayList<String> path=new ArrayList<String>();	
	
	
	public KMP(String main){		

		this.mainAry=new char[main.length()+1];
                System.arraycopy(main.toCharArray(),0,mainAry,1,main.length());
		this.next=new int[main.length()+1];
	}
	/**
	 * KMP匹配
	 * @param pos 从主串起始位置开始
	 */
	public String maxMatch(){

		failFunction();
		
		int i=mainAry.length-1;
		int j=1;
		String temp="";
		while(i>0&&j<mainAry.length){
			
			if(j==0||mainAry[i]==mainAry[j]){
				if(j!=0)
					temp=temp+mainAry[j]; //记录每一次想等的字符
				--i;
				++j;
			}else{
				array.add(temp); 
				temp="";
				j=next[j];
			}
		}
		
                String maxPreStr="";
                for(String s:array){
                      if(s.length>maxPreStr.length){
                              maxPreStr=s;
                      }
                }

                return maxPreStr;
		
	}
	/**
	 * 匹配串失效函数
	 */
	private void failFunction(){
		
		int i=1,j=0;
		next[1]=0;
		while(i<mainAry.length-1){
			if(j==0||mainAry[i]==mainAry[j]){
				next[++i]=++j;
			}else{
				j=next[j];
			}
		}
	}
	
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {
		
		SelfKMP kmp=new SelfKMP("acabaabaabcacaabc");
		System.out.println(kmp.maxMatch());
	}

}

      效率： 这个算法和KMP没有什么不同，因此n长度的T串最先需要付出O(n)代价来计算T的失效函数。然后需要O(n)来匹配前缀，最后付出O(x)代价来找最大字符串，其中x<n为所有满足条件的T前缀串的数量。