java 中模式匹配算法-KMP算法實例詳解

public class Pattern_KMP { 
 public static void main(String args[]) 
 { 
   int times; 
   String source="abcabaabcabcabxxzhabaabcabcabxad"; 
   String subStr="abcabx"; 
   times=pattren_KMP(source, subStr);    
   System.out.println("匹配次數(shù)："+times); 
 } 
  
 static int pattren_KMP(String source,String subStr) 
 { 
   int len1,len2; 
   len1=source.length(); 
   len2=subStr.length(); 
   int i,j; 
   i=j=0; 
   int times=0; 
   while(i<len1) 
   { 
     
     if(source.charAt(i)==subStr.charAt(j)) 
     { 
       
       i++; 
       j++; 
        
     }else  
     { 
       if(j==0)/*這一步很重要，如果沒有會進入死循環(huán)，也就是，如果主串某位與子串*/ 
         i++;/*第一位不等的話，必須往后移位。*/ 
       j=next(subStr,j); 
   
     } 
     if(j==len2) 
     { 
       times++; 
       j=0; 
        
     } 
       
   } 
   return times; 
 } 
 static int next(String subStr,int j) 
 { 
   if(j==0) 
     return 0; 
   else { 
     int next=0; 
     int k=1; 
     int m1; 
     int m2; 
     int i,n; 
     /*這一循環(huán)對應(yīng)實現(xiàn)上面函數(shù)的第二項*/ 
     while(k<j) 
     { 
       String sub1="",sub2=""; 
       for(m1=0,m2=j-k;m1<k&&m2<j;m1++,m2++) 
       { 
         sub1+=subStr.charAt(m1); 
         sub2+=subStr.charAt(m2); 
       } 
       
       for(i=0,n=0;i<sub1.length()&&n<sub2.length();i++,n++) 
       { 
         if(sub1.charAt(i)!=sub2.charAt(n)) 
           break; 
       } 
       if(i==sub1.length()&&n==sub2.length()) 
         next=k; 
       k++; 
     } 
    return next;  
   } 
        
 } 
} 

/* 通過計算返回子串T的next數(shù)組。 */ 
void get_next(String T, int *next)  
{ 
  int i,j; 
  i=1; 
  j=0; 
  next[1]=0; 
  while (i<T[0]) /* 此處T[0]表示串T的長度 */ 
  { 
    if(j==0 || T[i]== T[j])   /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */ 
    { 
      ++i;  
      ++j;  
      next[i] = j; 
    }  
    else  
      j= next[j]; /* 若字符不相同，則j值回溯 */ 
  } 
} 
 
/* 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)返回值為0。 */ 
/* T非空，1≤pos≤StrLength(S)。 */ 
int Index_KMP(String S, String T, int pos)  
{ 
  int i = pos;    /* i用于主串S中當(dāng)前位置下標(biāo)值，若pos不為1，則從pos位置開始匹配 */ 
  int j = 1;     /* j用于子串T中當(dāng)前位置下標(biāo)值 */ 
  int next[255];   /* 定義一next數(shù)組 */ 
  get_next(T, next); /* 對串T作分析，得到next數(shù)組 */ 
  while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環(huán)繼續(xù) */ 
  { 
    if (j==0 || S[i] == T[j])  /* 兩字母相等則繼續(xù)，與樸素算法增加了j=0判斷 */ 
    { 
      ++i; 
      ++j;  
    }  
    else      /* 指針后退重新開始匹配 */ 
      j = next[j];/* j退回合適的位置，i值不變 */ 
  } 
  if (j > T[0])  
    return i-T[0]; 
  else  
    return 0; 
}