Question

一道c语言的题目 急求代码

一个字符串，包含n个字符。写一个函数，用指向字符串的指针在此字符串中找出匹配的子字符串， 并将其替换成别的字符（与子字符串等长），如果没有匹配的子字符串，则输出匹配失败信息

Answer 1

#include<stdio.h>
#include <string.h>
void Index(char S[],char T[],int pos,int next[])//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
{ //其中，T非空，1<=pos<=S[0]
int i=pos,j=1;
while(i<=S[0]&&j<=T[0])
{ if(j==0||S[i]==T[j])
{ ++i;
++j;
}
else j=next[j];
}
if(j>=T[0]) printf("模式串在主串中的位置是： %3d\n\n",i-T[0]);
else printf("主串中不存在和模式串相等的字串");
}
void main()
{char S[]=" ababbaabaa";//0号单元存放字符串中字符的个数
char T[]=" aab";//0号单元存放字符串中字符的个数
int i,j,pos=0;
int next[100];//next[i]表示当模式中第i个字符和主串中相应的字符‘失配’时，
//在模式串中需重新和主串中该字符进行比较的字符的位置
S[0]=strlen(S)-1;
T[0]=strlen(T)-1;
printf("S[0]=%d\n",S[0]);
printf("T[0]=%d\n",T[0]);
i=1;
next[1]=0;
j=0;
while(i<T[0])
{ if(j==0||T[i]==T[j])
{ ++i;
++j;
next[i]=j;
}
else j=next[j];
}
for(i=1;i<=T[0];i++)
printf("%3d",next[i]);
printf("\n\n请输入您要从主串中的哪个字符开始查找：");
scanf("%d",&pos);
Index(S,T,pos,next);
}

//可以运行,我刚做好的

//以上是我参考的，以下是我数据结构的老师提供的ppt摘录的，希望你能理解

子串的定位操作通常称做串的模式匹配（其中T称为模式串），是各种串处理系统中的重要操作之一。下面给出采用定长顺序存储结构下不依赖于其他串操作的匹配算法。
下面讨论以定长顺序结构表示串时的几种模式匹配算法。

1.简单算法
2.KMP(D.E.Knuth,V.R.Pratt,J.H.Morris) 算法
3. 首尾匹配算法

int Index(SString S, SString T, int pos)
{ // 返回子串T在主串S中第pos个字符之后的位置。若不存在，
//则函数值为0。 其中，T非空，1≤pos≤StrLength(S)。
i = pos; j = 1;
while (i <= S[0] && j <= T[0])
{ if (S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符
else { i = i-j+2; j = 1; } // 指针后退/回溯重新开始匹配
}
if (j > T[0]) return i-T[0]; // j=T[0]+1 ; i-k+1=j ;
else return 0; // k=i-T[0]
} // Index

例如：
S=〃000000000000000000001〃
T=〃0000001”

解决办法：考虑回溯有没有必要，改进算法！

2. 模式匹配的一种改进算法--- KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 克努特-莫里斯-普拉特

假设主串S=′S1S2S3…Sn′ ，模式串P=′P1P2…Pm′ ，在主串中的第i个字符和模式串中的第j个字符比较时失配，即Si≠Pj
S1S2S3…Si-j+1Si-j+2…Si-2Si-1Si…Sn
= ≠ (1)
P1 P2 …Pj-2Pj-1Pj

S1S2S3…Si-k+1Si-k+2…Si-2 Si-1 Si…Sn
= (2)
P1 P2 …Pk-2Pk-1Pk
int Index_KMP(SString S, SString T, int pos) {
// 1≤pos≤StrLength(S)
i = pos; j = 1;
while (i <= S[0] && j <= T[0]) {
if (j = 0 || S[i] == T[j]) { ++i; ++j; }
// 继续比较后继字符
else j = next[j]; // 模式串向右移动
}//while
if (j > T[0]) return i-T[0]; // 匹配成功
else return 0;
} // Index_KMP

求 next 函数值的过程是一个递推过程，
分析如下:

已知：next[1] = 0；
假设：next[j] = k；又 T[j] = T[k]
则： next[j+1] = k+1
若： T[j]  T[k]
则 需往前回朔，检查 T[j] = T[ ？]
这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串

void get_next(SString &T, int &next[ ] ) {
// 求模式串T的next函数值并存入数组next。
i = 1; next[1] = 0; j = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j])
{++i; ++j; next[i] = j; }
else j = next[j];
}
} // get_next

还有一种特殊情况需要考虑：
例如：
S = aaabaaabaaaabaaabaaab
T = aaaab
next[j]= 01234

void get_nextval(SString &T, int &nextval[ ]) {
i = 1; nextval[1] = 0; j = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++i; ++j;
if (T[i] != T[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
} // get_nextval

3.首尾匹配算法

基本思想：
先比较模式串的第一个字符，
再比较模式串的最后一个字符，
最后比较模式串中从第二个
到第 n-1 个字符

int Index_FL(SString S, SString T, int pos) {
sLength = S[0]; tLength = T[0];
i = pos;
patStartChar = T[1]; patEndChar = T[tLength];
while (i <= sLength – tLength + 1) {
if (S[i] != patStartChar) ++i; //重新查找匹配起始点
else if (S[i+tLength-1] != patEndChar) ++i;
// 模式串的〃尾字符”不匹配
else { 在下页 }
}
return 0;
}// Index_FL

k = 1; j = 2;
while ( j < tLength && S[i+k] == T[j])
{ ++k; ++j; }
if ( j == tLength ) return i;
else ++i;
// 重新开始下一次的匹配检测

好累呀，还有很多图片贴不上，都是从ppt上复制粘过来的。。

Answer 2

#include <stdio.h>
#include <string.h>

/*定义一个函数，用指向字符串的指针匹配子字符串*/
int match(char * str, char * str1, char * str2, char * a_str);

int main()
{

/*定义两个字符数组，分别存储主字符串和子字符串*/
char mother[256],child[256];
/*定义一个字符串，用于替换子字符串*/
char change[256];
/*定义一个字符串，保存替换后的字符串*/
char af_change[256]="";
/*定义一个整型值，记录匹配结果*/
int result;

printf("匹配字符串：\n");
printf("请输入主字符串：\n");
gets(mother);
printf("请输入子字符串：\n");
gets(child);
printf("请输入替换的字符串：\n");
gets(change);
result=match(mother,child,change,af_change);
if (result==1)
{

printf("匹配和替换均成功！\n");
printf("替换后的字符串是：%s\n",af_change);

}
else if (result==0)

printf("匹配成功但替换失败！\n");

else

printf("匹配失败！\n");

return 0;

}

/*定义一个函数，用指向字符串的指针匹配子字符串*/
int match(char * str, char * str1, char * str2, char * a_str)
{

/*定义两个整型变量表示字符串的长度*/
int l1,l2;
/*定义指向字符串的指针,其中q1指向子字符串在主串中的位置，q2指向子字符串的位置*/
char * p, * q1=NULL,* q2,* t;
/*定义一个指向替换后的字符串指针*/
char *cc;
char *change[256];/*保存匹配成功时，子串在母串中的位置*/
int i,j; /*循环控制变量*/

/*对子串在母串中的位置进行初始化*/
for (i=0; i<256; i++) change[i]=NULL;

/*求出字符串的长度*/
l1=strlen(str1);
l2=strlen(str2);

/*对指针进行赋值*/
p=str;

/*字符串匹配过程*/
i=0;
for (p; *p!='\0'; p++)
{

q1=p;
q2=str1;
while ((*q2!='\0')&&(*q2==*q1))
{

q1++;
q2++;

}
if (*q2=='\0')/*匹配成功*/
{

change[i]=q1-l1;
i++;

}

}
if (i==0) /*匹配失败*/

return -1;

/*匹配成功后进行字符串替换过程*/
if (l1!=l2) /*替换后的字符串与原子字符串长度不等，无法替换*/
return 0;
cc=a_str;
p=str;
for (j=0; j<i; j++)/*对匹配的多个子串进行替换*/
{

while (p<change[j])/*复制母串中匹配前的字符*/
{

*a_str=*p;
a_str++;
p++;

}
for (t=str2; *t!='\0'; a_str++,t++) /*替换子字符串*/

*a_str=*t;

p+=l1;

}
if (*p!='\0') /*全部匹配字符串都替换完了，但母串未结束*/
while (*p!='\0')
{

*a_str=*p;
a_str++;
p++;

}
*a_str='\0';
a_str=cc;
return 1;

}

Answer 3

用KMP(D.E.Knuth, V.R.Pratt,J.H.Morris) 算法比较简单，可惜我也没用过，算法如下：

int Index_KMP(SString S, SString T, int pos) {
// 1≤pos≤StrLength(S)
i = pos; j = 1;
while (i <= S[0] && j <= T[0]) {
if (j = 0 || S[i] == T[j]) { ++i; ++j; }
// 继续比较后继字符
else j = next[j]; // 模式串向右移动
}
if (j > T[0]) return i-T[0]; // 匹配成功
else return 0;
} // Index_KMP

void get_next(SString &T, int &next[] ) {
// 求模式串T的next函数值并存入数组next
i = 1; next[1] = 0; j = 0;
while (i < T[0]) {
if (j = 0 || T[i] == T[j])
{++i; ++j; next[i] = j; }
else j = next[j];
}
} // get_next

void get_nextval(SString &T, int &nextval[]) {
i = 1; nextval[1] = 0; j = 0;
while (i < T[0]) {
if (j = 0 || T[i] == T[j]) {
++i; ++j;
if (T[i] != T[j]) next[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
} // get_nextval

Answer 4

楼上的,别讲KMP了,一看楼主就不懂,还是用简单查找替换吧

Answer 5

你要举个例子这样才清楚点嘛