Ⅰ 在主字元串中查找子串的KMP演算法和字元串中查找字元用KMP演算法的C語言代碼
/***KMP演算法是對蠻力演算法的優化，原理很簡單。但存在最壞情況，時間復雜度很可能會崩壞到(m+n)。
* 推薦在高頻度數據查找採用優化的Boyer-Moore演算法。
*以下為代碼
***/
/***首先創建一個ADT，這里給出最簡形式，省略部分涉及不到的操作***/
ADT String
{voidStrAssign（SString &T，char*S）//值為S的串T
bool SreEmpty(SString &S) //判斷空串
int StrLength(SString &s) //返回長度
void Concat (SString &T,SString&S1,SString &S2)//返回組合的新串
void SubString (SString &Sub,SString &S,int pos, int len)//同串則返回第pos後的串的最初位置，否則為0
}
/***演算法部分***/
int KMP(char *T,char *p)
{int n=strlen(T);
int m=strlen(P);
int i,j;
for(i=0;i<n-m;i++)
{j=0;
while(j<m&&T[i+j]==P[j])j++;
if(j==m) return i;
}
return -1}
Ⅱ java kmp演算法中的 kmp 是什麼意思
kmp演算法
一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。
如今，大夥基本上都用嚴蔚敏老師的書，那我就以此來講解KMP演算法。(小弟正在備戰考研，為了節省時間，很多課本上的話我都在此省略了，以後一定補上。)
嚴老的《數據結構》79頁講了基本的匹配方法，這是基礎。先把這個搞懂了。
80頁在講KMP演算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認識。目的在於指出「由此，在整個匹配的過程中，i指針沒有回溯，」。
我們繼續往下看：
現在討論一般情況。
假設 主串：s: 『s(1) s(2) s(3) ……s(n)』 ; 模式串 ：p: 『p(1) p(2) p(3)…..p(m)』
把課本上的這一段看完後，繼續
現在我們假設 主串第i個字元與模式串的第j(j<=m)個字元『失配』後，主串第i個字元與模式串的第k(k<j)個字元繼續比較
此時，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我們得到關系式
『p(1) p(2) p(3)…..p(j-1)』 = 』 s(i-j+1)……s(i-1)』
由於s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：(k<j),
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(i-k+1)s(i-k+2)……s(i-1)』
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比較)
匹配串： P(1) p(2) …… p(k-1) p(k)
現在我們把前面總結的關系綜合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比較)
P(1) p(2) ……. p(k-1) p(k)
由上，我們得到關系：
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(j-k+1)s(j-k+2)……s(j-1)』
接下來看「反之，若模式串中存在滿足式(4-4)。。。。。。。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。(偽代碼)
K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
課本83頁不是有個例子嗎？就是 圖4.6
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
然後找幾道練習題好好練練，一定要做熟練了。現在你的腦子里已經有那個next演算法的初步思想了，再回去看它是怎麼推出來的，如果還看不懂，就繼續做練習，做完練習再看。相信自己！！！
附：
KMP演算法查找串S中含串P的個數count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //遞推計算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函數求T在主串S中的個數count的KMP演算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
補上個Pascal的KMP演算法源碼
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函數用於模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0
不再贅述演算法原理，下面是兩個函數，已經通過測試，可以直接用。
private int[] get_nextval(String t) {
int len = t.length();
int i = 0;
int j = -1;
int next[] = new int[len];
while (i < len - 1) {
if (j == -1 || (t.charAt(i) == (t.charAt(j)))) {
i++;
j++;
if (t.charAt(i) != (t.charAt(j))) {
next[i] = (j + 1);
} else {
next[i] = next[j];
}
} else {
j = (next[j] - 1);
}
}
return next;
}
private int index_KMP(String s, String t, int[] next) {
int i = 0;
int j = 0;
while (i < s.length() - 1 && j < t.length() - 1) {
if (j == 0 || (s.charAt(i) == t.charAt(j))) {
i++;
j++;
} else
j = (next[j] - 1);
}
if (j > t.length() - 2) {
return (i - t.length() + 1);
} else
return -1;
}
Ⅲ 用KMP演算法寫的完整程序，麻煩您了
自己寫的測試了幾個結果是對的
性能沒有好的數據測試
僅供參考，主要靠你自己
/////////////////////////////////c++////////////////////////////////////////////////////
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int *next;
string mString;
string nString;
void getNext(string n)
{
next=new int[n.length()];
char nHead=n[0];
for(int j=0;j<n.length();j++)
{
next[j]=0;
for(int i=j-1;i>(j)/2;i--)
{
if(n[i]==nHead)
{
int tHead=i;
int tEnd=j-1;
int count=0;
for(int h=tHead;h<=tEnd;h++)
{
if(n[count++]!=n[h])
break;
}
if((count==tEnd-tHead+1)&&n[count]!=n[j])
next[j]=count;
}
}
}
}
int main()
{
cout<<"input main String please!"<<endl;
cin>>mString;
cout<<"input sub String please!"<<endl;
cin>>nString;
getNext(nString);
int pos;//第一個匹配模式的首字母的實際位置
for(int i=0,j=0;i<=mString.length()&&j<=nString.length();)
{
if(j==nString.length())
{
pos=i-j+1;
cout<<"successed and start postion is "<<pos<<endl;
delete[]next;
return 0;
}
if(mString[i]!=nString[j])
{
if(j==0)
i++;
else
j=next[j];
}
else
{
i++;
j++;
}
}
cout<<"failed!"<<endl;
delete[]next;
return 0;
}
Ⅳ 求kmp演算法的詳細解釋。（最好附上能運行的程序）
t;i),那麼next[i]就是所有這樣的j的最大值
形象地說,就是假如第i 1個字元匹配失敗之後,下一個可能匹配位置至少應該往後挪動多少
就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0
計算過程基本上抄自演算法導論,假設str長度為n
k=0;//k表示當前匹配了多少位
next[1]=0;
for (i=1;in;i )
{
while (k
Ⅳ java中String的int indexof(String)方法是用什麼演算法實現的，是KMP嗎
不是KMP演算法，自己看看源碼就知道了。
至於原因:
KMP對特殊的字元串比較好用 就是自身帶有很多重復子串的那種
在字元串不長的情況下 KMP比較耗時
Ⅵ kmp演算法完整代碼（C++）謝謝！
剛學應該仔細看書，首先要學會自己用手一步一步模擬計算的過程，把中間步驟記錄下來，作為測試用例。復雜演算法居然直接看代碼，你認為自己很牛嗎？
Ⅶ kmp模式Java編程需要學嗎
kmp模式，是指進行字元串比較：
此演算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現的，因此該演算法被稱為克努斯-莫里斯-普拉特操作，簡稱為KMP演算法。
KMP演算法，是不需要對目標串S進行回溯的模式匹配演算法。讀者可以回顧上面的例子，整個過程中完全沒有對目標串S進行回溯，而只是對模式串T進行了回溯。通過前面的分析，我們發現這種匹配演算法的關鍵在於當出現失配情況時，應能夠決定將模式串T中的哪一個字元與目標串S的失配字元進行比較。所以呢，那三位前輩就通過研究發現，使用模式串T中的哪一個字元進行比較，僅僅依賴於模式串T本身，與目標串S無關。
這里就要引出KMP演算法的關鍵所在next數組，next數組的作用就是當出現失配情況S[i] != T[j]時，next[j]就指示使用T中的以next[j]為下標的字元與S[i]進行比較（注意在KMP演算法中，i是永遠不會進行回溯的）。還需要說明的是當next[j] = -1時，就表示T中的任何字元都不與S[i]進行比較，下一輪比較從T[0]與S[i+1]開始進行。由此可見KMP演算法在進行模式匹配之前需要先求出關於模式串T各個位置上的next函數值。即next[j]，j = 0,1,2,3,...n-1。
如果你是研究底層演算法的話，要了解一下，如果你是做應用開發的話，了解一下就可以了，這是數據結構方面的內容。
Ⅷ KMP演算法詳細代碼
private int KMP(String inText, String inMode)
{
if (inText.Length < inMode.Length)
{
return -1;
}
int[] arrNext = new int[inMode.Length + 1];
this.Next(inMode, arrNext);
int i, j; // i是主串游標 j是模式串游標
for (i = j = 0; i < inText.Length && j < inMode.Length; )
{
if (j == -1 || // 模式串游標已經回退到第一個位置
inText[i] == inMode[j]) // 當前字元匹配成功
{ // 滿足以上兩種情況時兩個游標都要向前進一步
++i;
++j;
}
else // 匹配不成功,模式串游標回退到當前字元的arrNext值
{
j = arrNext[j];
}
}
if (j >= inMode.Length)
{
return i - inMode.Length;
}
else
{
return -1;
}
}
private void Next(String inMode, int[] arrNext)
{
arrNext[0] = -1;
for (int i = 0, j = -1; i < inMode.Length; )
{ // i是主串游標 j是模式串的游標
if (j == -1 || // 如果模式串游標已經回退到第一個字元
inMode[i] == inMode[j]) // 如果匹配成功
{ // 兩個游標都向前走一步
++i;
++j;
arrNext[i] = j; // 存放當前的arrNext值為此時模式串的游標值
}
else // 匹配不成功j就回退到上一個arrNext值
{
j = arrNext[j];
}
}
}
Ⅸ KMP演算法 看看代碼哪裡錯了
搞定了請採納最佳答案
#include<stdio.h>
#include<string.h>
voidgetnext(charT[],int*next)
{
inti,j;
i=0;
j=-1;
next[0]=-1;
while(i<strlen(T))
{
if(j==-1||T[i]==T[j])
{
next[i+1]=j+1;
i++;
j++;
}
else
j=next[j];
}
}
intKMP(charS[],charT[])
{
inti=0,j=0,next[100];
getnext(T,next);
while(i<strlen(S)&&j<strlen(T))
{
if(j==0||S[i]==T[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j>=strlen(T))
returni-strlen(T);
else
return-1;
}
voidmain()
{
charS[100],T[100];
printf("請輸入主字元串S ");
gets(S);
printf("請輸入子字元串T ");
gets(T);
printf("位置%d",KMP(S,T));
}
Ⅹ 急！kmp演算法代碼
LZ的get_next函數和Index_KMP函數的代碼是復制粘貼的吧，那對應的是字元數組下標以1開始的代碼，此外也有少量錯誤，修改後的正確代碼如下。另外，LZ的代碼中找不到next數組的定義，並且元素類型應該int才對頭，這點需要在適當位置補充。
voidget_next(HString&T,int*next)
{
inti=0,j=-1;
next[0]=-1;/////關鍵
while(i<T.length-1)
{
if(j==-1||T.ch[i]==T.ch[j])
{
++i;
++j;
//////////////改進版KMP增加此判斷/////////
if(T.ch[i]==T.ch[j])
next[i]==next[j];
else
////////////////////////////////////////////
next[i]==j;
}
else
j=next[j];
}
}
intIndex_KMP(HString&S,HString&T,intpos)
{
inti=pos,j=0;
get_next(T,next);
while(i<S.length&&j<T.length)
{
if(j==-1||S.ch[i]==T.ch[j])
{
++i;
++j;
}
else
j=next[j];
}
if(j>=T.length)
returni-T.length;//返回的匹配位置從下標0起算
else
return-1;//返回-1表示沒有找到
}