A. 一道c语言的题目 急求代码
#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上复制粘过来的。。
B. 《数据结构（C语言版）》之“串的模式匹配算法”
# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# define OK 1
# define ERROR 0
typedef int Status;
//串的定长顺序存储结构
# define MAX_STR_LEN 40
typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度
Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的个数
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos个字符起长度为len的子串
Status SubString(SString Sub,SString S,int pos,int len)
{
int i;
if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
{
return ERROR;
}
for (i=1; i<=len; ++i)
{
Sub[i] = S[pos+i-1];
}
Sub[0] = len;
return OK;
}
//输出字符串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函数值并存入数组next
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 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];
}
}
}
//利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
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])
{
return i - T[0];
}
else
{
return 0;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串为：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串为：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d个字符处首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的从第5个字符起长度为5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2为:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的输出结果：
------------------------
主串为：a a a b a a a a b
子串为：a a a a b
子串的next的数组为：0 1 2 3 4
主串和子串在第5个字符处首次匹配
子串的nextval数组为：0 0 0 0 4
主串和子串在第5个字符处首次匹配
求串s1的从第5个字符起长度为5的子串s2:
串s2为:a a a a b
Press any key to continue
------------------------------
*/
C. 急！！急！！急！！数据结构（C语言版）程序设计题： 使用KMP算法实现一个模式匹配。
#include <cstring>
#include <iostream>
using namespace std;
//修正后的求next数组各值的函数代码
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0; //i是从0开始的
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循环的if部分
{
++i;
++j;
if( ptrn[i] != ptrn[j] ) //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else //循环的else部分
j = nextval[j];
}
}
void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)
{
cout<<src_index<<"\t"<<src<<endl;
cout<<pstr_index<<"\t";
for( int i = 0; i < src_index-pstr_index; ++i )
cout<<" ";
cout<<pstr<<endl;
cout<<endl;
}
//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式匹配函数
//输入：src, slen主串
//输入：patn, plen模式串
//输入：nextval KMP算法中的next函数值数组
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
{
int i = pos;
int j = 0;
while ( i < slen && j < plen )
{
if( j == -1 || src[i] == patn[j] )
{
++i;
++j;
}
else
{
j = nextval[j];
//当匹配失败的时候直接用p[j_next]与s[i]比较，
//下面阐述怎么求这个值，即匹配失效后下一次匹配的位置
}
}
if( j >= plen )
return i-plen;
else
return -1;
}
int main()
{
std::string src = "";
std::string prn = "abac";
int* nextval = new int[prn.size()];
//int* next = new int[prn.size()];
get_nextval(prn.data(), prn.size(), nextval);
//get_next(prn.data(), prn.size(), next);
for( int i = 0; i < prn.size(); ++i )
cout<<nextval[i]<<"\t";
cout<<endl;
cout<<"result sub str: "<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;
system("pause");
delete[] nextval;
return 0;
}
望楼主采纳！