1.BF算法

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include "string.h"
    4. // 返回子串T在主串S中的位置
    5. // 若不存在，则返回0
    6. // T非空，1 <= strlen(S)
    8. int index( char* S, char* T)
    9. {
    10.     int i = 0;    // i用于主串S中当前位置下标
    11.     int j = 0;      // j用于子串T中当前位置下标
    13.     while( i <= strlen(S) && j < strlen(T) ) // i或j其中一个到达尾部即终止搜索！
    14.     {
    15.         if( S[i] == T[j] )  // 若相等则继续下一个元素匹配
    16.         {
    17.             i++;
    18.             j++;
    19.         }
    20.         else                // 若失配则j回溯到第一个元素从新匹配
    21.         {
    22.             i = i-j+2;      // i回溯到上次匹配首位的下一个元素，这是效率低下的关键！
    23.             j = 0;
    24.         }
    25.     }
    27.     if( j >= strlen(T) )
    28.     {
    29.         return i - strlen(T);
    30.     }
    31.     else
    32.     {
    33.         return -1;
    34.     }
    35. }
    36. int main()
    38. {
    39.     int a;
    40.     char* S = "012345rtyuio";
    41.     char* T = "rtyu";
    42.     a = index(S,T);
    43.     printf("%d",a);
    45.     return 0;
    46. }

    image.png