字符串匹配 KMP 算法 Java实现

字符串匹配过程中，如果使用蛮力算法，效率非常的差，在此介绍一种较为高效的匹配算法KMP算法。
其主要思想是从匹配的模版去分析，即去分析Pattern串的自身规律，进而去优化匹配的效率。例如字符串“ababcb”，明显看出是ab出现一组重复，若出现如下匹配模式：
        text：abababcb
     pattern: ababcb
此时发生错误，一般情况下会选择移动Pattern一个位置来继续，事实证明效果不佳。聪明的人一眼就看出来，下一步应该进行这样的匹配
          text：abababcb
       pattern:   ababcb
        通过一次移动两个位置便迅速完成匹配，而移动的位置大小也恰恰是ab这个重复串的大小，所以，匹配每次移动的位置一定和当前字符串的真前缀真后缀有关，根据科学家实验，移动的位置==最大相等真前后缀的长度，此时我们需要一个和模版一样长的数组去存放Pattern下次要移动的位置，我们称Nexd[]。
对于Parrern:"a  b a b c b" 这个模版来讲，
    它的next[]: -1 0 0 1 2 0
其中数字next[i]代表下次模版需要用Pattern[next[i]]去匹配text,而-1代表整个模版直接跳过当前字符。所以，算法的关键其实就是算出next[].

public class KMP
{
	public KMP()
	{
		
	}
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		String text = "ab abcb ababcb abab cb ababcb ababc ";
		String pattern ="ababcb";
		showList(getNext(pattern));
		kmpScan(text, getNext(pattern), pattern);
	}
	
	
	public static void kmpScan(String str, int[] next,String pattern)
	{
		int k =0;
		int j =0;
		int count =0;
		int index =0;
		//int[] index = new int[count];
		while(k<str.length())
		{
			
			if(j==-1&&k<str.length())
			{
				k++;
				j=0;
			}
			else if(str.charAt(k)==pattern.charAt(j))
			{	
				j++;
				k++;
			}
			else{
				j=next[j];
			}
			if(j==pattern.length())
			{
				index = k-j;
				j=0;
				k++;
				count++;
				System.out.println(index);//记录了字符出现的位置
			}
			
		}
		System.out.println(count);
	}
	public static int[] getNext(String pattern)
	{
		char[] pat = pattern.toCharArray();
		int[] next = new int[pattern.length()];
		next[0]=-1;
		next[1]=0;
		for (int i = 2; i < next.length; i++)
		{
			int k=next[i-1];
			while(k>=0)
			{	
				if(pat[k]==pat[i-1]) 
					break;
				k=next[k];
			}
			next[i]=k+1;
		}
		return next;
	}
	public static void showList(int next[])
	{
		for (int i = 0; i < next.length; i++)
		{
			System.out.printf("%d ",next[i]);
		}
		System.out.println();
	}
}

结果：
-1 0 0 1 2 0
8
23
2

结论：一种高效的算法，在英文匹配上比较出色，也可以将其用在byte匹配上~
      另一种更高效的算法BM,期待下一篇~

已有 0 人发表留言，猛击->> 这里<<-参与讨论


ITeye推荐

• —软件人才免语言低担保 赴美带薪读研！—