串的匹配模式

串S和T存在,T是非空串， l<=pos<=s.strLength (s)
若主串S中存在和串T值相同的子串， 则返回它在主串S中
第pos个字符之后第一次出现的位置 ， 否则返回0。

朴素的模式匹配

```
/*
朴素的模式匹配：基本数组实现
假设主串S和要匹配的子串T的长度存在S[0]与T[0]中
*/
/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。
T非空，1≤pos≤StrLength (s)*/
int Index(String S,String T,int pos)
{
    int i = pos;
    int j=1;
    while(i<=S[0] && j<=T[0]){
        if(S[i] == T[j]){
            ++i;
            ++j;
        }else{
            i=i-j+2;//i退回到上次匹配首位的下一位
            j=1;//j退回到子串T的首位
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}
```

KMP模式匹配

```
/*
KMP模式匹配算法实现
*/
//通过计算返回子串T的next数组。
//char T[100] = "xxxxxx";字符串的本质就是数组
void get_next(char *T,int *next)
{
    int i,j;
    i=1;//因为T[0]存储了T的长度，所以从1开始
    j=0;//next值
    next[1]=0;//next数组从下标为1开始 默认next[0]=0
    while(i<T[0]){//T[0]表示串T的长度
        if(j==0||T[i]==T[j]){
            i++;
            j++;
            next[i]=j;
        }else{
            //若T[i]!=T[j]字符不相同，则回溯...->0
            j = next[j];

        }
    }
}
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。
//T非空，1SposSStrLength(s)。
int Index_KMP(String S,String T,int pos)
{
    int i = pos;//i用于主串S当前位置下标值
    int j=1;//j用于子串T中当前位置下标值
    int next[255];
    get_next(T,next);//对串T作分析，得到next数组
    while(i<=S[0] && j<=T[0]){
        if(j==0||S[i] == T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];//j T的对比位置退回到next中的位置
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}
```

KMP 模式匹配算法改进

```
/*
KMP 模式匹配算法改进
get_next()——>get_nextval()
Index_KMP()不变
*/
//通过计算返回子串T的next数组。
//char T[100] = "xxxxxx";字符串的本质就是数组
void get_nextval(char *T,int *next)
{
    int i,j;
    i=1;//因为T[0]存储了T的长度，所以从1开始
    j=0;//next值
    next[1]=0;//next数组从下标为1开始 默认next[0]=0
    while(i<T[0]){//T[0]表示串T的长度
        if(j==0||T[i]==T[j]){
        /* T[i]表示后缀的单个字符，*/
        /* T[j]表示前缀的单个字符*/
            i++;
            j++;
            if(T[i]!=T[j]){//若当前字符与前缀字符不同
                next[i]=j;//则当前的门为nextval在i位置的值
            }else{
                next[i] = next[j];//如果与前缀字符相同，则将前缀
                                //字符的nextval值赋值给nextval在i位置的值
            }
        }else{
            //若T[i]!=T[j]字符不相同，则回溯...->0
            j = next[j];

        }
    }
}
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。
//T非空，1SposSStrLength(s)。
int Index_KMP(String S,String T,int pos)
{
    int i = pos;//i用于主串S当前位置下标值
    int j=1;//j用于子串T中当前位置下标值
    int next[255];
    get_nextval(T,next);//对串T作分析，得到next数组
    while(i<=S[0] && j<=T[0]){
        if(j==0||S[i] == T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];//j T的对比位置退回到next中的位置
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}
```