串的定位操作通常稱作串的模式匹配，是各種處理系統(tǒng)中的最重要操作之一。
模式匹配最樸素的算法是回溯法，即模式串跟主串一個字符一個字符的匹配，當(dāng)模式串中跟主串不匹配時，主串回溯到與模式串匹配開始的下一個位置，模式串回溯到第一個位置，繼續(xù)匹配。算法的時間復(fù)雜度為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;} //如果相同，則繼續(xù)向后比較
else
{i = i-j+1; j =0;} //如果不同，就回溯，重新查找
}
if (j == strlen(T))
return i-strlen(T); //若匹配成功，返回S中與T字符串相同開始位置的索引
else return 0; //若匹配不成功，返回0
}
O（m*n）的時間復(fù)雜度有點大，于是人們發(fā)現(xiàn)了KMP算法，核心思想是：當(dāng)不匹配發(fā)生時，主串不回溯，模式串回溯到“合適”的位置，哪個位置合適，只與模式串有關(guān)，所以可以先算出模式串中各個字符，當(dāng)不匹配發(fā)生是，應(yīng)該回溯到哪個位置。算法整體時間復(fù)雜度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的操作不是最優(yōu)的，因為他沒有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會出現(xiàn)大量的1，這樣的算法復(fù)雜度已經(jīng)和最初的樸素算法沒有區(qū)別了。所以稍微改動一下：
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]; //減少回退次數(shù)
else next[i] = j; //和上面算法一樣next[i]=j
}
else j = next[j];
}
}
