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()函数，函数本身包含了模式串的局部匹配信息。