子串的定位操作通常称做串的模式匹配，是串中最重要的操作之一。

    假设我们要从下面的主串S=”goodgoogle”中，找到T=”google”这个子串的位置。

    我们通常需要下面的步骤:

    1. 主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是g。第一位匹配失败。如图5-6-1所示，其中竖直连线表示相等，闪电状弯折连线表示不等。

    image.png

    1. 主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图5-6-2所示。

    image.png

    1. 主串S第三位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图5-6-3所示。

    image.png

    1. 主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败，如图5-6-4所示。

    image.png

    1. 主串S第五位开始，S与T，6个字母全匹配，匹配成功，如图5-6-5所示。

    image.png
    简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。

    前面我们已经用串的其他操作实现了模式匹配的算法Index。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。

    实现代码如下：

    1. /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
    2. /* T非空，1≤pos≤StrLength(S)。 */
    3. int Index(String S, String T, int pos){
    5.     /* i用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配 */
    6.     int i = pos;
    8.     /* j用于子串T中当前位置下标值 */
    9.     int j = 1;
    11.     /* 若i小于S长度且j小于T的长度时循环 */
    12.     while (i <= S[0] && j <= T[0]){
    14.         /* 两字母相等则继续 */
    15.         if (S[i] == T[j]){
    17.             ++i;
    18.             ++j;
    20.         }
    21.         /* 指针后退重新开始匹配 */
    22.         else{
    24.             /* i退回到上次匹配首位的下一位 */
    25.             i = i - j + 2;
    26.             /* j退回到子串T的首位 */
    27.             j = 1;
    29.         } 
    31.     }
    33.     if (j = T[0])
    34.         return i - T[0];
    35.     else
    36.         return 0;
    38. }

    分析一下，最好的情况是什么？那就是一开始就区配成功，比如“googlegood”
    中去找“google”，时间复杂度为O(1)。稍差一些，如果像刚才例子中第二、三、四位一样，每次都是首字母就不匹配，那么对T串的循环就不必进行了，比如“abcdef-google”
    中去找“google”。那么时间复杂度为O(n+m)，其中n为主串长度，m为要匹配的子串长度。根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。

    那么最坏的情况又是什么？就是每次不成功的匹配都发生在串T的最后一个字符。举一个很极端的例子。主串为S=”00000000000000000000000000000000000000000000000001”
    ，而要匹配的子串为T=”0000000001”，前者是有49个“0”和1个“1”的主串，后者是
    9个“0”和1个“1”的子串。在匹配时，每次都得将T中字符循环到最后一位才发现：哦，原来它们是不匹配的。这样等于T串需要在S串的前40个位置都需要判断10次，并得出不匹配的结论，如图5-6-6所示。
    image.png
    直到最后第41个位置，因为全部匹配相等，所以不需要再继续进行下去，如图5-6-7所示。如果最终没有可匹配的子串，比如是T=”0000000002”，到了第41位置判断不匹配后同样不需要继续比对下去。因此最坏情况的时间复杂度为O((n-m＋1)*m)。
    image.png
    不要以为我这只是危言耸听，在实际运用中，对于计算机来说，处理的都是二进位的0和1的串，一个字符的ASCII码也可以看成是8位的二进位01串，当然，汉字等所有的字符也都可以看成是多个0和1组成的串。再比如像计算机图形也可以理解为是由许许多多个0和1的串组成。所以在计算机的运算当中，模式匹配操作可说是随处可见，而刚才的这个算法，就显得太低效了。