首页 > 编程语言 > 详细

5月16日(优化链串BF算法、

时间:2019-05-16 18:48:08      阅读:154      评论:0      收藏:0      [点我收藏+]

优化链串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 }

5月16日(优化链串BF算法、

原文:https://www.cnblogs.com/L1Gd0ng/p/10877103.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!