疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

字符串匹配 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[].

  Java代码

  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

  {

  if(j==-1&&k

  {

  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匹配上~