The title

There is a primary string S = {a,b, C,a, C,a, B,d,c}, pattern string T = {a,b,d}; Find the position where the pattern string first appears in the main string; (Note: there is no need to consider string case, characters are all lowercase letters)

BF algorithm idea

BF, also known as Brute Force, has the following core ideas: Start from subscript 1, S [1] = A,T[1] = A, then continue to compare the same, until S [3] = C,T[3] = D, indicating that the match is not successful, the main subscript needs to go back to subscript 2, substring back to subscript 1, a new round of comparison. S [2] at this time! = T[1], the match is not successful. At this time, the subscript of the main string points to 3, and the substring falls back to the subscript 1, and the comparison continues until the complete match is successful.

BF algorithm implementation

#define OK 1 #define ERROR 0 #define MAXSIZE 40 /* Typedef int Status; /* typepedef char String[MAXSIZE+1]; /* typepedef char String[MAXSIZE+1]; */ Status StrInit(String T,char *chars) {if (strlen(chars) > MAXSIZE) {return ERROR; } T[0] = strlen(chars); for (int i = 1; i < T[0] + 1; i ++) { T[i] = *(chars+i-1); } return OK; Void StrPrint(String T) {for (int I = 1; i < T[0] + 1; i++) { printf("%c",T[i]); } printf("\n"); } /* BF algorithm */ int Index_BF(String S, String T,int pos){int I = pos; Int j = 1; // int j = 1; While (I <= S[0] &&j <= T[0]) {if (S[I] == T[j]) {I ++; if (S[I] == T[j]) {if (S[I] == T[j]) {I ++; j++; }else {// if the pointer is not equal, then the pointer is rematched. // If the pointer is rematched, then the pointer is rematched. // add 1, because the substring starts with 1; // Add one more element from the first bit of the last match; i = i-j+2; // return j to the first place of the substring T j = 1; If (j >T[0]) {if (j >T[0]) {return i-t [0]; if (j >T[0]) {return i-t [0]; }else{ return -1; } } int main(int argc, const char * argv[]) { @autoreleasepool { // insert code here... NSLog(@"Hello, World!" ); String s; StrInit(s, "abcacabdc"); String t; StrInit(t, "abd"); int index = Index_BF(s, t, 1); printf("index = %d\n",index); } return 0; }Copy the code

Advantages and disadvantages of BF algorithm

Advantages: violent, practical, simple code, easy to understand

Disadvantages: High time complexity, a lot of meaningless traversal, such as primary string “0000000000”, substring “000000001”