串的定位操作通常称作串的模式匹配，是各种处理系统中的最重要操作之一。

模式匹配最朴素的算法是回溯法，即模式串跟主串一个字符一个字符的匹配，当模式串中跟主串不匹配时，主串回溯到与模式串匹配开始的下一个位置，模式串回溯到第一个位置，继续匹配。算法的时间复杂度为O（m*n），算法如下：

复制代码 代码如下:

//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串

int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替

{

int i=pos, j=0;

while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度

{

if (S[i] == T[j])

{ ++i; ++j;} //如果相同，则继续向后比较

else

{i = i-j+1; j =0;} //如果不同，就回溯，重新查找

}

if (j == strlen(T))

return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引

else return 0; //若匹配不成功，返回0

}

O（m*n）的时间复杂度有点大，于是人们发现了KMP算法，核心思想是：当不匹配发生时，主串不回溯，模式串回溯到“合适”的位置，哪个位置合适，只与模式串有关，所以可以先算出模式串中各个字符，当不匹配发生是，应该回溯到哪个位置。算法整体时间复杂度O(m+m)。

算法如下：

复制代码 代码如下:

void GetNext(char* T, int *next)

{

int i=1,j=0;

next[1]=0;

while( i < strlen(T) )

{

if (j == 0 || T[i] == T[j])

{

++i; ++j;

next[i] = j;

}

else j = next[j];

}

}

int KMP(char* S, char* T, int pos)

{

int i = pos, j = 1;

while (i)

{

if (S[i] == T[j])

{

++ i; ++ j;

}

else

j = next[j];

}

if (j > strlen(T))

return i-T[0];

else

return 0;

}

求next的操作不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：

复制代码 代码如下:

void GetNextEx(char *T, int *next)

{

int i=1,j=0; next[1] = 0;

while(i < strlen(T))

{

if (j == 0 || T[i] == T[j])

{

++i; ++j;

if (T[i] == T[j])

next[i] = next[j]; //减少回退次数

else next[i] = j; //和上面算法一样next[i]=j

}

else j = next[j];

}

}