kmp演算法匹配
❶ kmp演算法匹配題，如圖，求解
下標從0開始的，當模式串的c失配時，就應該滑動模式串前面aba的a來比較，j就是2了，主串的下標i不變，就是5了
所以答案是C
❷ 什麼情況下，KMP演算法的性能會退化為樸素匹配演算法
（1）未改進的模式匹配演算法的時間復雜度為O（nm），但在一般情況下，其實際的執行時間接近O（n＋m），因此至今仍被採用。
（2）KMP演算法僅當模式與主串之間存在許多「部分」匹配的情況下才顯得比未改進的模式匹配快。
（2）KMP演算法的最大特點是指示主串的指針不需要回溯，在整個匹配過程中，對主串僅需要從頭至尾掃描一遍，這對處理存儲在外存上的大文件是非常有效的。
(2)kmp演算法匹配擴展閱讀：
KMP演算法是三位學者在 Brute-Force演算法的基礎上同時提出的模式匹配的改進演算法。Brute- Force演算法在模式串中有多個字元和主串中的若干個連續字元比較都相等,但最後一個字元比較不相等時，主串的比較位置需要回退。KMP演算法在上述情況下，主串位置不需要回退,從而可以大大提高效率。
如果模式P與目標T(或其子串)存在某種程度的相似,則認為匹配成功。常用的衡量字元串相似度的方法是根據一個串轉換成另一個串所需的基本操作數目來確定。基本操作由字元串的插入、刪除和替換來組成。
❸ kmp演算法什麼意思
KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指針i的回溯問題，只需確定下次匹配j的位置即可，使得問題的復雜度由O(mn)下降到O(m+n)。
在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數組，next[j]的值表示P[0...j-1]中最長後綴的長度等於相同字元序列的前綴。
對於next[]數組的定義如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1]
因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
❹ KMP模式匹配演算法
這里有個相似的問題，也是我回答的，講了原理
http://..com/question/329386416.html
如果你只要代碼的話
一個簡單的代碼
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);
char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;
int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}
int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}
void get_next(char *t,int *next)
{
int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}
❺ 什麼是KMP演算法
KMP就是串匹配演算法
運用自動機原理
比如說
我們在S中找P
設P＝{ababbaaba}
我們將P對自己匹配
下面是求的過程:{依次記下匹配失敗的那一位}
[2]ababbaaba
......ababbaaba[1]
[3]ababbaaba
........ababbaaba[1]
[4]ababbaaba
........ababbaaba[2]
[5]ababbaaba
........ababbaaba[3]
[6]ababbaaba
..............ababbaaba[1]
[7]ababbaaba
..............ababbaaba[2]
[8]ababbaaba
.................ababbaaba[2]
[9]ababbaaba
.................ababbaaba[3]
得到Next數組『0,1,1,2,3,1,2,2,3』
主過程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)轉[4]否則轉[3]
[3]若j=0或a[i]=b[j]則【inc(i)inc(j)轉[2]】否則【j:=next[j]轉2】
[4]若j>m則return(i-m)否則return -1;
若返回－1表示失敗，否則表示在i-m處成功
若還不懂mail:[email protected]
參考一下這里吧:
http://www.chinaaspx.com/archive/delphi/4733.htm
❻ 數據結構 字元串 模式匹配問題 KMP演算法
你的程序本身思路沒有錯，但錯在以下幾點：
1.在程序中有字元串S和T，你用S[0]代表字元串的長度，但S是字元串，S[0]是長度嗎？
2.在main函數中，你輸入的S和T都是用gets(S)或gets(T),那麼它們都是以下標0開頭的，你應該要進行處理，使它以下標1作為開頭（可以這樣gets(&S[1]); 然後S[0] = strlen(&S[1]) + '0';在用S[0]作為長度的時候，把它從字元變成數字就行了)。
❼ KMP匹配演算法
不懂得話，就自己跟上三四遍就好了，代碼附上
有什麼不懂的就問，不過還是盡量自己鑽研的好
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
const int maxLen = 128;
class String
{
int curLen; //串的當前長度
char *ch; //串的存儲數組
public:
String (const String & ob);
String (const char *init);
String ();
~String ()
{
delete [] ch;
}
int Length () const
{
return curLen;
}
String *operator () ( int pos, int len );
int operator == ( const String &ob )const
{
return strcmp (ch, ob.ch) == 0;
}
int operator != ( const String &ob ) const
{
return strcmp (ch, ob.ch) != 0;
}
int operator !() const
{
return curLen == 0;
}
String &operator = (const String &ob);
String &operator += (const String &ob);
char &operator [] (int i);
int fastFind ( String pat ) const;
//void fail (const char *T,int* &f);
void fail (int* &f);
};
String::String ( const String &ob ) //復制構造函數：從已有串ob復制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = ob.curLen;
strcpy ( ch, ob.ch );
}
String::String ( const char *init ) //復制構造函數: 從已有字元數組*init復制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = strlen (init);
strcpy ( ch, init );
}
String::String ( )//構造函數：創建一個空串
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = 0;
ch[0] = '\0';
}
String *String::operator ( ) ( int pos, int len )//從串中第pos個位置起連續提取len個字元//形成子串返回
{
String *temp = new String;
if ( pos < 0 || pos+len -1 >= maxLen|| len < 0 ) //返回空串
{
temp->curLen = 0;
temp->ch[0] = '\0';
}
else //提取子串
{
//動態分配
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串長度
for ( int i=0, j=pos; i<len; i++, j++ )
temp->ch[i] = ch[j]; //傳送串數組
temp->ch[len] = '\0'; //子串結束
}
return temp;
}
String &String::operator = ( const String &ob )//串賦值：從已有串ob復制
{
if ( &ob != this )
{
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ! ch )
{
cerr << "out of memory!\n ";
exit (1);
}
curLen = ob.curLen; //串復制
strcpy ( ch, ob.ch );
}
else
cout << "Attempted assignment of a String to itself!\n";
return *this;
}
char &String::operator [] ( int i ) //按串名提取串中第i個字元
{
if ( i < 0 && i >= curLen )
{
cout << "Out Of Boundary!\n ";
exit (1) ;
}
return ch[i];
}
String &String::operator += ( const String &ob )
{ //串連接
char * temp =ch; //暫存原串數組
curLen += ob.curLen; //串長度累加
ch = new char [maxLen+1];
if ( ! ch )
{
cerr << "Out Of Memory!\n ";
exit (1) ;
}
strcpy ( ch, temp ); //拷貝原串數組
strcat ( ch, ob.ch ); //連接ob串數組
delete [ ] temp;
return *this;
}
int String :: fastFind ( String pat ) const //帶失效函數的KMP匹配演算法
{
int posP = 0, posT = 0;
int lengthP = pat.curLen, lengthT = curLen;
int *f=new int[lengthP];
memset(f,-1,lengthP);
pat.fail (f);
while ( posP < lengthP && posT < lengthT )
{
if ( pat.ch[posP] == ch[posT] )
{
posP++;
posT++; //相等繼續比較
}
else if ( posP == 0 )
{
posT++;
}//不相等
else
{
posP = f[posP-1]+1;
}
}
delete []f;
if ( posP < lengthP )
return -1;
else
return posT - lengthP;
}
void String::fail (int* &f)//計算失效函數
{
int lengthP = curLen;
f[0] = -1; //直接賦值
for ( int j=1; j<lengthP; j++ ) //依次求f [j]
{
int i = f[j-1];
if ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //遞推
if ( *(ch+j) == *(ch+i+1) )
f [j] = i+1;
else
f [j] = -1;
}
}
/**/
void main()
{
int end;
cout<<"hello!\n";
String s1("acabaabaabcacaabc");
String s2=("abaabcac");
end=s1.fastFind(s2);
cout<<end<<endl;
}
❽ kmp演算法的串匹配演算法
輸入： 正文串T[1,n]和模式串W[1,m]
輸出： 匹配結果match[1,n] intKMP(stringW,stringT){inti=1,j=1;while(i<=n){while(j!=0&&W[j]!=T[i]){j=next[j];}if(j==m){returni-m+1;//success,returnthefirstmatchposition}else{j++;i++;}}return-1;//failure}procereKMPbegini=1j=1whilei<=ndowhilej<>0andW[j]<>T[i]doj=newnext[j]endwhileifj=mreturn「success」elsej++i++endifendwhilereturn「failure」end
❾ kmp演算法的介紹
KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數，函數本身包含了模式串的局部匹配信息。