字符串匹配算法(C/Java实现) ╰+攻爆jí腚メ 2024-04-01 14:52 18阅读 0赞 #### 目录 #### * BF算法 * * C语言实现 * Java实现 * KMP算法 * * Java实现 * C语言实现 * next\[\]数组的优化 ## BF算法 ## BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。 > 该算法最坏情况下要进行M\*(N-M+1)次比较,[时间复杂度][Link 1]为O(MN)。 ![image-20221017113326969][] ### C语言实现 ### #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include <assert.h> #include<string.h> //字符串匹配算法 BF KMP //str 主串 sub 子串 //返回值:返回子串在主串中的下标,如果不存在就返回-1 int BF(char* str,char* sub) { assert(str != NULL && sub != NULL); if (str == NULL || sub == NULL) { return -1; } int lenStr = strlen(str); int lenSub = strlen(sub); int i = 0; int j = 0; while (i < lenStr && j < lenSub) { if (str[i] == sub[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if (j >= lenSub)//j走完了子串 { return i - j; } return -1; } int main() { printf("%d\n", BF("ababcabcdabcde", "abcd"));//5 printf("%d\n", BF("ababcabcdabcde", "abcdef"));//-1 printf("%d\n", BF("ababcabcdabcde", "ab"));//0 return 0; } ### Java实现 ### public class Test { public static int BF(String str,String sub){ if(str==null||sub==null){ return -1; } int lenStr=str.length(); int lenSub=sub.length(); if(lenStr==0||lenSub==0){ return -1; } int i=0;//遍历主串 int j=0;//遍历子串 while(i<lenStr&&j<lenSub){ if(str.charAt(i)==sub.charAt(j)){ i++; j++; }else{ i=i-j+1; j=0; } } if(j>=lenSub){ return i-j; } return -1; } public static void main(String[] args) { System.out.println(BF("ababcabcdabcde","abcd"));//5 System.out.println(BF("ababcabcdabcde","abcdef"));//-1 System.out.println(BF("ababcabcdabcde","ab"));//0 } } ## KMP算法 ## ![在这里插入图片描述][72831cc336df4a5c95373931c7dfb043.gif_pic_center] KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。 > 为了减少匹配次数,匹配失败时i,j的回退位置变了 KMP的精髓就是next数组:也就是用next\[j\]=k来表示。如果匹配失败,子串j要移动到k的位置重新开始匹配。 > k的值是这样求的:在范围\[0,j-1\]内找到匹配成功部分的两个相等的真子串(不包括本身)。k=真子串的长度 > > 不管什么数据,next\[0\]=-1;next\[1\]=0; ![image-20221104214008302][] > 练习1:对于"ababcabcdabcde",求其next\[\]数组? > > \-1 0 0 1 2 0 1 2 0 0 1 2 0 0 > > (发现0,1,2增加是均匀增加的) > > 练习2:对“abcabcabcabcdabcde",求其next\[\]数组? > > \-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0 **接下来的问题是,已知next\[i\]=k,怎么求next\[i+1\]=?** ![image-20221104204146646][] ### Java实现 ### public class Test { //构建next[]数组 public static int[] getNext(String sub) { int lenSub = sub.length(); int[] next = new int[lenSub]; next[0] = -1; next[1] = 0; int k = 0; int i = 2; while(i < lenSub) { if(k == -1 || sub.charAt(k) == sub.charAt(i-1)) { next[i] = k+1; i++; k++; } else { k = next[k]; } } return next; } public static int KMP(String str, String sub, int pos) { if(str == null || sub == null) { return -1; } int len1 = str.length(); int len2 = sub.length(); if(len1 == 0 || len2 == 0) { return -1; } int i = pos; int j = 0; int[] next = getNext(sub); while(i < len1 && j < len2) { if(j == -1 || str.charAt(i) == sub.charAt(j)) { i++; j++; } else { j = next[j]; } } if(j >= len2) { return i-j; } return -1; } public static void main(String[] args) { System.out.println(kmp("ababcabcdabcde","abcd",0)); System.out.println(kmp("ababcabcdabcde","abcdf",0)); System.out.println(kmp("ababcabcdabcde","ab",0)); } } ### C语言实现 ### #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> void getNext(char* sub, int* next, int lenSub) { next[0] = -1; next[1] = 0; int i = 2; int k = 0; while (i < lenSub) { if (k==-1||sub[i - 1] == sub[k]) { next[i] = k + 1; i++; k++; } else { k = next[k]; } } } int KMP(char* str,char* sub,int pos) { assert(str != NULL && sub != NULL); int lenStr = strlen(str); int lenSub = strlen(sub); if (lenStr == 0 || lenSub == 0) return -1; int i = pos;//遍历主串 int j = 0;//遍历字串 int* next = (int*)malloc(sizeof(int) * lenSub); getNext(sub,next,lenSub); while (i < lenStr && j < lenSub) { if (j==-1||str[i] == sub[j]) { i++; j++; } else { j = next[j];//匹配失败j回退 } } if (j >= lenSub) { return i - j; } //主串走完了还没匹配成功 return -1; } int main() { printf("%d\n", KMP("ababcabcdabcde","abcd",0));//5 printf("%d\n", KMP("ababcabcdabcde","abcdf",0));//-1 printf("%d\n", KMP("ababcabcdabcde","ab",0));//0 return 0; } ### next\[\]数组的优化 ### ![image-20221104213608388][] 练习: ![image-20221104213352529][] [Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6?fromModule=lemma_inlink [image-20221017113326969]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9e9bf25ee713486eb6fe53a174893489.png [72831cc336df4a5c95373931c7dfb043.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/61b63cfb6f38417ba5176077e87554d9.gif [image-20221104214008302]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/de2c69028abe4e909a51f700c7b09a0f.png [image-20221104204146646]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ffcbbed6b2374db4be7ba0ace68eb020.png [image-20221104213608388]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5603181bc11c4176b3541798ad916115.png [image-20221104213352529]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/907dc3ea4f75492488828a0bd3eeb3ae.png
还没有评论,来说两句吧...