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;
}
望樓主採納！