#include <iostream>
#include <string>
using namespace std;
void findPreStr(char comp [],int move[])
{
int strlen=0;
while (comp[strlen]!='\0')
{
++strlen;
}
int matchnum=0;
move[1]=0;
for (int index=2;index<strlen+1;++index)
{
while (matchnum>0&&comp[matchnum]!=comp[index-1])
{
matchnum=move[matchnum];
}
if (comp[index-1]==comp[matchnum])
{
++matchnum;
}
move[index]=matchnum;
}
}
//数据结构书中的方法 待修正
void getNextVal(char *str,int move[])
{
int len=strlen(str);
int index=0;
int matchnum=1;
move[0]=0;
move[1]=0;
while (index<len)
{
if (matchnum==0||str[index]==str[matchnum])
{
++index;
++matchnum;
if (str[index]!=str[matchnum])
{
move[index]=matchnum;
}
else
{
move[index]=move[matchnum];
}
}
else
{
matchnum=move[matchnum];
}
}
}
//下边求覆盖函数的算法是我自己的想法
void computePre(char * str,int move[])
{
int length=strlen(str);
move[0]=0;
move[1]=0;
for (int index=1;index<length;++index)
{
if (move[index]==0)
{
if (str[index]==str[0])
{
move[index+1]=1;
}
else
{
move[index+1]=0;
}
}
else
{
if (str[index]==str[move[index]])
{
move[index+1]=move[index]+1;
}
else
{
move[index+1]=0;
}
}
}
}
void matchfun(char * source,char * matchstr,int fun[])
{
int length=strlen(source);
if (length<strlen(matchstr))
{
cout<<"fail find substr"<<endl;
return;
}
int matchnum=0;
int sumnumber=0;
bool findflag=false;
for (int index=0;index<length; )
{
int curindex=index;
while(source[curindex]==matchstr[matchnum])
{
++matchnum;
++curindex;
//++sumnumber;
}
if (matchnum==strlen(matchstr))
{
findflag=true;
cout<<index<<":"<<matchstr<<endl;
}
if(matchnum)
{
index+=matchnum-fun[matchnum];
matchnum=0;
}
else
{
++index;
}
++sumnumber;
}
if (!findflag)
{
cout<<"fail find substr"<<endl;
}
cout<<length<<":"<<sumnumber<<endl;
}
void otherMatch(char * source,char * matchstr,int fun[])
{
int len1=strlen(source);
int len2=strlen(matchstr);
if (len1<len2)
{
cout<<"match error"<<endl;
return;
}
int matchnum=1;
int index=0;
while (matchnum<len2&&index<len1)
{
if (matchnum==0||source[index]==matchstr[matchnum])
{
index++;
matchnum++;
}
else
{
matchnum=fun[matchnum];
}
}
if (matchnum==len2)
{
cout<<"match success:"<<index-len2<<endl;
}
else
{
cout<<"match fail:"<<endl;
}
}
//普通的匹配方法
void isInclude(char * source,char * com)
{
int len1=strlen(source);
int len2=strlen(com);
for (int i=0;i<len1;++i)
{
int index=i;
for (int j=0;j<len2;++j)
{
if (source[index]!=com[j])
{
break;
}
++index;
}
if (j==len2)
{
cout<<"match success: "<<i<<endl;
}
}
}
void main()
{
char * source="kaacckkkkkkkkkkaaccddaabbmkkkkkkkkkkkkkk";
char* com="aacck";
int move[30];
isInclude(source,com);
computePre(com,move);
//findPreStr(com,move);
//getNextVal(com,move);
cout<<source<<endl;
cout<<com<<endl;
for (int i=1;i<strlen(com)+1;++i)
{
cout<<move[i];
}
cout<<endl;
matchfun(source,com,move);
otherMatch(source,com,move);
}
