程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> C# KMP算法字符串匹配

C# KMP算法字符串匹配

編輯:關於C#

命題:設計算法,在字符串s中,從pos位置開始,查找第一個與目標字符串t相同的子字符串的起始位置。

kmp算法實現:第一步,預處理目標字符串t,求出t中每一個字符在與源字符串s中字符不等時移到的位置。方法是根據如下公式

next[0]=-1;
next[j]=max{k|0<k<j&&"t0t1...t(k-1)"=="t(j-k)t(j-k+1)...t(j-1)"};
next[j]=0;

此公式可如下證明

首先,假設目標字符串下一次移動到k位置,那麼這個k位置有什麼特性呢,k之前的所有字符(k個,從0開始),應該和源字符串s中i位置前的k個字符相同,即:

"t0t1...t(k-1)"=="s(i-k)s(i-k+1)...s(i-1)"

而且,這時候,源字符串i位置之前的k個字符和目標字符串j位置之前的k個字符也相同,即:

"t(j-k)t(j-k+1)...t(j-1)"=="s(i-k)s(i-k+1)...s(i-1)"

那麼得到如下結論

"t0t1...t(k-1)"=="t(j-k)t(j-k+1)...t(j-1)"

第二步,循環源字符串和目標字符串,如下吧,這段不好說了

while(s[i] != ’’ && t[j] != ’’)
{
if(j == -1 || s[i] == t[j]) //j==-1表示s[i]與t[0]不同
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(t[j] == ’’)
return i-j;
else
return 0;
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved