优化链串BF算法

1 //串的模式匹配（BF算法）s1为主串s2为子串s3为最后结果的串的位置  2 int stringBF(linkstr *s1,linkstr *s2,linkstr *s3){ 3     linkstr *ls,*s,*st,*lst; 4     lst = s1; 5     st = s2; 6     s = s2; 7     int i = 0;  8     while(s->next != NULL){ 9         s = s->next;10         i++; 11     }12     while(ls->next != NULL){13         ls = lst;14         s = st;15         while(s->next->next != NULL){16             if(s->ch != ls->ch) break;17             else{18                 s = s->next;19                 ls = ls->next;20                 if(s == NULL){21                     s3 = st;22                     return 1;23                 } 24             }25         }26         lst = lst->next;27     }28     for(int j = 0; jnext; 30     } 31     st->next = NULL; 32     return -1;33 }

顺序串的KMP算法  

1//父串为 f = "abcabcdabcdeabcdefabcdefg"  子串为 s = "abcdeabcdefab"   2 int Index_KMP(char f[],char s[]){ 3     int i=0,j=0,re; 4      5     for(re = 0;s[0] == s[re] || s[re] =='\0';re++)　　　　　　/*记录子串中与父串相等的字符位置*/ 6      7     while(1){ 8          9         if(s[j] == '\0' || f[i] == '\0') break;  /*当子串或父串到底时结束循环*/10         if(f[i] == s[j]){　　　　　　　　11             while(1){12                 i++;13                 j++;14                 if(s[j] == '\0') return i-j+1;      /*当子串到底时返回i-j+1个元素的位置*/15                 if(s[j] != f[i]) {　　　　　　　　　　　　/*当子串与父串对应的值不相等时，判断子串是否超过了与第一个字符相等的字符*/16                     if(j>=re){17                         i = i+re; 　　　　　　　　　　　　　　18                         j = 0; 19                     } 20                     else{21                         i = i+1-j;22                         j = 0;23                     }24                 }25                 break; 26             } 27         }28         else29             i++; 30     } 31     32     if(f[i] == '\0') return -1; 　　　　　　/*若父串到底子串还未到底则父串中没有子串*/33     34     35      36 }