#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上复制粘过来的。。
参考资料：http://zhidao.baidu.com/question/26712670.html