字符串的定位操作通常称为串的模式匹配。模式匹配的应用很常见的函数模式一般是：
int index(const string &Tag, const string &Ptn, int pos)
其中，Tag是主字符串，Ptn是子字符串，如果在主串Tag的第pos个位置后存在与子字符串Ptn相同的子串，返回它在主串第pos个字符后第一次出现的位置，否则返回-1。
一、BF算法：
暴风(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。如图所示：
二、KMP算法：
BF算法的时间复杂度最坏情况是o（Plen*Tlen），而之所以时间复杂度是由于索引指针的回溯引起的，针对以上不足，于是出现了KMP算法。它的时间复杂度为o（Plen+Tlen）。改进之处在于：每一趟比较重出现的字符不等时，不需要回溯索引指针i，而是利用已经得到的部分匹配结果将子串向右滑动尽可能远的距离，继续进行比较。
如果采用简单的BF算法，则每趟比较i都会要退回，而采用KMP算法，每趟比较时，保持不变，只需要将j向右滑动即可，可即减少了中间一些趟次的比较。
//求next数组中各元素的值，保存在长为len的next数组中void get_next(const string &Ptn, int *next, int len){int j = 0;int k = -1;next[0] = -1;while (j<len - 1){if (k == -1 || Ptn[j] == Ptn[k]){ //如果满足上面分析的Pk = Pj的情况，则继续比较下一个字符，//并得next[j+1]=next[j]+1j++;k++;next[j] = k;}else{ //如果符合上面分析的第2种情况，则依据next[k]继续寻找下一个比较的位置k = next[k];}}}//求next数组的改进数组中各元素的值，保存在长为len的nextval数组中void get_nextval(const string &Ptn, int *nextval, int len){int j = 0;int k = -1;nextval[0] = -1;while (j<len - 1){if (k == -1 || Ptn[j] == Ptn[k]){ //如果满足上面分析的Pk = Pj的情况，则继续比较下一个字符，//并得next[j+1]=next[j]+1j++;k++;if (Ptn[j] != Ptn[k])nextval[j] = k;else //Ptn[j]与Ptn[k]相等时，直接跳到netval[k]nextval[j] = nextval[k];}else{ //如果符合上面分析的第2种情况，则依据next[k]继续寻找下一个比较的位置k = nextval[k];}}}/*返回子串Ptn在主串Tag的第pos个字符后(含第pos个位置)第一次出现的位置，若不存在，则返回-1采用KMP算法，这里的位置全部以从0开始计算为准，其中T非空，0<=pos<=Tlen*/int kmp_index(const string &Tag, const string &Ptn, int pos){int i = pos; //主串当前正待比较的位置，初始为posint j = 0; //子串当前正待比较的位置，初始为0int Tlen = Tag.size(); //主串长度int Plen = Ptn.size(); //子串长度//求next数组的值，并逐个输出int *next = (int *)malloc(Plen * sizeof(int));get_next(Ptn, next, Plen);//get_nextval(Ptn,next,Pln);int t;cout << "子串的next数组中的各元素为：";for (t = 0; t<Plen; t++)cout << next[t] << " ";cout << endl;while (i<Tlen && j<Plen){if (j == -1 || Tag[i] == Ptn[j]){ //如果当前字符相同，或者在子串的第一个字符处失配，则继续向下比较i++;j++;}else //如果当前字符不同，则i保持不变，j变为下一个开始比较的位置{//next数组时KMP算法的关键，i不回退，//而是继续与子串中的next[j]位置的字符进行比较j = next[j];}}if (j >= Plen)return (i - Plen);elsereturn -1;}(没有写好，有时间再写，未完待续！)