#include "stdio.h"
#include "string.h"
#include "stdlib.h"
const int n=200;
int c[n][n];
char str[n];
#define MaxSize 100
typedef struct
{
char data[MaxSize];
int length; //串长
}SqString;
void StrAssign(SqString &str,char cstr[]) //str为引用型参数
{
int i;
for (i=0;cstr[i]!='\0';i++)
str.data[i]=cstr[i];
str.data[i]='\0';
str.length=i;
}
void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值
{
int j=0,k=-1;
nextval[0]=-1;
while(j-1 || t.data[j]==t.data[k])
{
j++;
k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}
else k=nextval[k];
}
}
int KMPIndex1(SqString s,SqString t,int start) //修正的KMP算法
{
int nextval[MaxSize],i=0,j=0;
GetNextval(t,nextval);
i=start;
while(i-1 || s.data[i]==t.data[j])
{
i=i+1;
j++;
}
else
j=nextval[j];
}
if (j>=t.length)
return (i-t.length);
else
return -1;
}
int lcs_len(char a[],char b[],int c[][n])
{
int sa=strlen(a);
int sb=strlen(b);
int i,j;
for(i=0;i<=sa;i++)
c[i][0]=0;
for(j=0;j<=sb;j++)
c[0][j]=0;
for(i=1;i<=sa;i++)
{
for(j=1;j<=sb;j++)
{
if(a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if(c[i][j-1]> c[i-1][j])
c[i][j]=c[i][j-1];
else c[i][j]=c[i-1][j];
}
}
return c[sa][sb];
}
char* bulid_lcs(char a[],char b[])
{
int k=0,i,j;
i=strlen(a);
j=strlen(b);
k=lcs_len(a,b,c);
str[k]= '\0 ';
while(k>0)
{
if(c[i][j]==c[i-1][j])
i--;
else if(c[i][j]==c[i][j-1])
j--;
else
{
str[--k]=a[i-1];
i--;
j--;
}
}
return str;
}
void main()
{
char a[n],b[n],z[n],f[n],change[n];
SqString s,t,st;
int p[n],q[n],m,i=1,j,j1,j2,k,h,start,flag1,flag2;
printf("Please enter three strings!\n");
printf("Please enter first string X: ");
gets(a);
printf("Please enter second string Y: ");
gets(b);
printf("Please the new string Z: ");
gets(z);
StrAssign(s,a);
StrAssign(t,b);
StrAssign(st,z);
start = 0,j1=0;
flag1=flag2=-1;
while(1) //求子串Z在主串X中的所有位置，并记录
{
if(start>=s.length)
break;
m=KMPIndex1(s,st,start);
if(m!=-1)
{
flag1=1;
printf("字符串Z在字符串X中第%d次匹配的位置为:%d\n",i++,m);
p[j1++]=m;
start = m+st.length;
}
else
break;
}
start = 0,j2=0,i=1;
while(1) //求子串Z在主串Y中的所有位置，并记录
{
if(start>=t.length)
break;
m=KMPIndex1(t,st,start);
if(m!=-1)
{
flag2=1;
printf("字符串Z在字符串Y中第%d次匹配的位置为:%d\n",i++,m);
q[j2++]=m;
start = m+st.length;
}
else
break;
}
if(flag1==-1 && flag2==-1)
printf("无法匹配！\n"); //不匹配的时候
bulid_lcs(a,b);
if(str[0]==' ')
printf("这两个字符串没有公共字符串！\n");
else
{
printf("The max length common subsequence is: ");
puts(str); //找出X和Y的一个最长公共子串
}
if(flag1==1 || flag2==1)
{
printf("请输入任意的串去置换X和Y中的子串Z：\n");
gets(change);
if(flag1==1) //替换X中的字串Z
{
k=0;
for(i=0;i"%c",a[k]);
for(j=0;j"%c",change[j]);
k+=st.length;
}
for(;k"%c",a[k]);
printf("\n");
}
if(flag2==1) //替换Y中的字串Z
{
k=0;
for(i=0;i"%c",b[k]);
for(j=0;j"%c",change[j]);
k+=st.length;
}
for(;k"%c",b[k]);
printf("\n");
}
}
system("pause");
}
void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值
{
int j=0,k=-1;
nextval[0]=-1;
while(j-1 || t.data[j]==t.data[k])
{
j++;
k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}
else k=nextval[k];
}
}
int KMPIndex1(SqString s,SqString t,int start) //修正的KMP算法
{
int nextval[MaxSize],i=0,j=0;
GetNextval(t,nextval);
i=start;
while(i-1 || s.data[i]==t.data[j])
{
i=i+1;
j++;
}
else
j=nextval[j];
}
if (j>=t.length)
return (i-t.length);
else
return -1;
}
这两个函数没发全