串的基本操作
#include<iostream>
#define Maxlen 255
using namespace std;
typedef struct{
char ch[Maxlen];
int length;
}SString;
//求子串
bool SubString(SString &Sub,SString S,int pos,int len)
{
if(pos+len-1>S.length)//子串范围越界
return false;
for(int i=pos;i<pos+len;i++)
{
Sub.ch[i-pos+1]=S.ch[i];
}
Sub.length=len;
return true;
}
//比较操作
int StrCompare(SString S,SString T)
{
for(int i=1;i<=S.length && i<=T.length ;i++)
{
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
}
//若所有字符都相等,则比较长度
return S.length-T.length;
}
//定位操作,寻找子串位置
int index(SString S,SString T)
{
int i=1;
int n=S.length,m=T.length;
SString sub;
while(i<=n-m+1)
{
SubString(sub,S,i,m);
if(StrCompare(sub,T)!=0) ++i;//比较子串是否相等
else return i;
}
return 0; //不存在相等子串
}
两种模式匹配算法
朴素模式匹配算法
//朴素模式匹配算法
int Index(SString S,SString T)
{
int i,j=1;
while(i<=S.length && j<=T.length)
{
if(S.ch[i] == T.ch[j])
++i,++j;//继续比较后续字符
else{
i=i-j+2;//i回到当前子串的第二位开始重新匹配
j=1; //重新回退到第一位开始匹配
}
}
if(j>T.length)
return i-T.length;
else return 0;
}
时间复杂度为O(mn)
最坏情况:每个模式串的每一位都要比较,共n-m+1个子串,故复杂度为O(m*(n-m+1))=O(nm-m^2+m)=O(nm)
KMP算法
int Index_KMP(SString S,SString T,int next[])
{
int i,j=1;
while(i<=S.length && j<=T.length)
{
if(j==0 || S.ch[i] == T.ch[j])
++i,++j;//继续比较后续字符
else{
j=next[j];
}
}
if(j>T.length)
return i-T.length;
else return 0;
}
最坏时间复杂度O(m+n)
求模式串的next数组
任何模式串都是next[1]=0,next[2]=1;
next数组的其他位:在不匹配的位置前,划一条分界线
然后模式串一位一位往右移,直到分界线之前“能对上”,或者模式串完全跨国分界线为止。此时j指向哪里,next数组值就是多少。
例1:求aaaab的next数组
next[1] | next[2] | next[3] | next[4] | next[5] |
---|---|---|---|---|
0 | 1 | 2 | 3 | 4 |
例2:求ababaa的next数组
next[1] | next[2] | next[3] | next[4] | next[5] | next[6] |
---|---|---|---|---|---|
0 | 1 | 1 | 2 | 3 | 4 |
求nextval数组
先求next数组,再由next数组求nextval数组
nextval[1]=0;
for(int j=2;j<=T.length;j++)
{
if(T.ch[next[j]]==T.ch[j])
nextval[j]=nextval[next[j]];
else
nextval[j]=next[j];
}
标签:,return,int,next,length,数组,SString
From: https://www.cnblogs.com/Jinx8823/p/17528791.html