溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
java 中模式匹配算法-KMP算法實例詳解
樸素模式匹配算法的最大問題就是太低效了。于是三位前輩發表了一種KMP算法，其中三個字母分別是這三個人名的首字母大寫。
簡單的說，KMP算法的對于主串的當前位置不回溯。也就是說，如果主串某次比較時，當前下標為i,i之前的字符和子串對應的字符匹配，那么不要再像樸素算法那樣將主串的下標回溯，比如主串為“abcababcabcabcabcabc”,子串為“abcabx”.第一次匹配的時候，主串1,2,3,4,5字符都和子串相應的匹配，第6為‘c'與子串中的‘x'不匹配，說明此時i=6,下次匹配的時候，就不用再像樸素那樣，將i置為2，再循環置為3,4,5去和子串匹配了。而是直接從i=6(以i=6為開頭)開始和子串去進行匹配。
那么子串的下標的變化呢，是不是每次要從第一位開始去和主串匹配，實際上也不需要。還是上面的例子，第一次匹配后，子串的當前位置（下標）為j=6,因為前兩位a,b和主串的4,5位的a,b已經比較完成，是匹配的，所以這兩位也無需比較，也就是從j=3開始和主串匹配。現在的問題是，如何找到子串的下標j的變化。
我們把子串各個位置的j值得變化定義為1個數組next，那么next的長度就是T串的長度。于是可以得到下面的函數定義：
上圖引用自《大話數據結構》，關于更多的KMP算法的說明，尤其是next[j]的推導，讀者可以參考該書，講解的非常的詳細。下面給出該算法的java實現。
在《大話數據結構》，保存串的數組的首位，也就是0下標位置保存的是字符串的長度。但是上面的next[j]卻可取值為0,這點我沒有弄明白，如有哪位牛人能幫忙解釋，萬分感謝。下面編寫的代碼略有不同，在0下標位置不再是保存字符串的長度，而是保存字符串的首字符，也就是是與字符串對應的。所以next[j]的計算函數也不太一樣,如下：
實現的代碼：
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("匹配次數："+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)/*這一步很重要，如果沒有會進入死循環，也就是，如果主串某位與子串*/
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;
/*這一循環對應實現上面函數的第二項*/
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;
}
}
}
下面附上《大話數據結構》中的KMP算法（c代碼）供對照參考（不是完整可執行程序）
/* 通過計算返回子串T的next數組。 */
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個字符之后的位置。若不存在，則函數返回值為0。 */
/* T非空，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos)
{
int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */
int j = 1; /* j用于子串T中當前位置下標值 */
int next[255]; /* 定義一next數組 */
get_next(T, next); /* 對串T作分析，得到next數組 */
while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */
{
if (j==0 || S[i] == T[j]) /* 兩字母相等則繼續，與樸素算法增加了j=0判斷 */
{
++i;
++j;
}
else /* 指針后退重新開始匹配 */
j = next[j];/* j退回合適的位置，i值不變 */
}
if (j > T[0])
return i-T[0];
else
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
