基础kmp应用,找到所有匹配位置即可

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
char t[],f[],aim[];
int mark[],next[];
bool myequal(char a,char b)
{
if(a >= 'A' && a <= 'Z')
a = a-'A'+'a';
if(b >= 'A' && b<= 'Z')
b = b-'A'+'a';
if(a == b)return true;
else return false;
}
void makenext(const char *p)
{
int q,k;
int m = strlen(p);
next[] = ;
for(q = ,k = ;q < m;q++)
{
while(k > && !myequal(p[q],p[k])) k = next[k-];
if(myequal(p[q],p[k])) k++;
next[q] = k;
}
}
void kmp(const char *t,const char *p)
{
int n,m,i,q;
n = strlen(t),m = strlen(p);
makenext(p);
for(i = ,q = ;i < n;i++)
{
while(q > && !myequal(p[q],t[i])) q = next[q-];
if(myequal(p[q],t[i])) q++;
if(q == m) mark[i-m+] = ;
}
}
int main()
{
while(gets(f))
{
gets(aim);
gets(t);
memset(mark,,sizeof(mark));
memset(next,,sizeof(next));
kmp(t,f);
int lent = strlen(t),lenjump = strlen(f);
for(int i = ;i < lent;i++)
{
if(mark[i])
{
cout<<aim;
i += lenjump-;
}
else cout<<t[i];
}
cout<<endl;
}
return ;
}
04-26 17:08
查看更多