題目: 有一個(gè)主串S = {a, b, c, a, c, a, b, d, c}, 模式串T 式串在主串中第一次出現(xiàn)的位置;
提示: 不需要考慮字符串大小寫問題, 字符均為小寫字母;
代碼實(shí)現(xiàn)：
代碼準(zhǔn)備：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲(chǔ)空間初始分配量 */
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼序芦，如OK等 */
typedef int ElemType; /* ElemType類型根據(jù)實(shí)際情況而定臭杰，這里假設(shè)為int */
typedef char String[MAXSIZE+1]; /* 0號(hào)單元存放串的長(zhǎng)度 */
//----字符串相關(guān)操作---
/* 生成一個(gè)其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* 令串長(zhǎng)為零 */
return OK;
}
/* 輸出字符串T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
/* 返回串的元素個(gè)數(shù) */
int StrLength(String S)
{
return S[0];
}
獲取next數(shù)組
void get_next(String T,int *next){
int i,j;
j = 1;
i = 0;
next[1] = 0;
//abcdex
//遍歷T模式串, 此時(shí)T[0]為模式串T的長(zhǎng)度;
//printf("length = %d\n",T[0]);
while (j < T[0]) {
//printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//T[i] 表示后綴的單個(gè)字符;
//T[j] 表示前綴的單個(gè)字符;
++i;
++j;
next[j] = i;
//printf("next[%d]=%d\n",j,next[j]);
}else
{
//如果字符不相同,則i值回溯;
i = next[i];
}
}
}
//輸出Next數(shù)組值
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
匹配算法
int count = 0;
//KMP 匹配算法(1)
//返回子串T在主串S中第pos個(gè)字符之后的位置, 如不存在則返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串當(dāng)前位置的下標(biāo)準(zhǔn),j是模式串當(dāng)前位置的下標(biāo)準(zhǔn)
int i = pos;
int j = 1;
//定義一個(gè)空的next數(shù)組;
int next[MAXSIZE];
//對(duì)T串進(jìn)行分析,得到next數(shù)組;
get_next(T, next);
count = 0;
//注意: T[0] 和 S[0] 存儲(chǔ)的是字符串T與字符串S的長(zhǎng)度;
//若i小于S長(zhǎng)度并且j小于T的長(zhǎng)度是循環(huán)繼續(xù);
while (i <= S[0] && j <= T[0]) {
//如果兩字母相等則繼續(xù),并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配時(shí),j回退到合適的位置,i值不變;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
對(duì)獲取next數(shù)組進(jìn)行優(yōu)化
void get_nextVal(String T,int *nextVal){
int i,j;
j = 1;
i = 0;
nextVal[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
++j;
++i;
//如果當(dāng)前字符與前綴不同,則當(dāng)前的j為nextVal 在i的位置的值
if(T[i] != T[j])
nextVal[j] = i;
else
//如果當(dāng)前字符與前綴相同,則將前綴的nextVal 值賦值給nextVal 在i的位置
nextVal[j] = nextVal[i];
}else{
i = nextVal[i];
}
}
}
優(yōu)化后匹配算法
int Index_KMP2(String S,String T,int pos){
//i 是主串當(dāng)前位置的下標(biāo)準(zhǔn),j是模式串當(dāng)前位置的下標(biāo)準(zhǔn)
int i = pos;
int j = 1;
//定義一個(gè)空的next數(shù)組;
int next[MAXSIZE];
//對(duì)T串進(jìn)行分析,得到next數(shù)組;
get_nextVal(T, next);
count = 0;
//注意: T[0] 和 S[0] 存儲(chǔ)的是字符串T與字符串S的長(zhǎng)度;
//若i小于S長(zhǎng)度并且j小于T的長(zhǎng)度是循環(huán)繼續(xù);
while (i <= S[0] && j <= T[0]) {
//如果兩字母相等則繼續(xù),并且j++,i++
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配時(shí),j回退到合適的位置,i值不變;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
