优化链串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; j<i ;j++){ 29 st = st->next; 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 else 29 i++; 30 } 31 32 if(f[i] == ‘\0‘) return -1; /*若父串到底子串还未到底则父串中没有子串*/ 33 34 35 36 }
原文:https://www.cnblogs.com/L1Gd0ng/p/10877103.html