原题链接：数据结构-KMP字符串模式匹配算法实现
解题思路: 写一个kmp算法的方法 多调用几遍方法就好了
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | import java.util.Scanner;public class KMP字符串模式匹配算法实现 { public static void main(String[] args) { // 3组字符串，每组字符串占一行。每行包含由空格分隔的两个字符串，字符串仅由英文小写字母组成且长度不大于100。 // 每组数据输出1行，输出后一个字符串在前一个字符串中的位置，如果不匹配，则输出0。 Scanner sc = new Scanner(System.in); String[][] arr = new String[3][2]; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { arr[i][j] = sc.next(); } } int[] next1 = kmpNext(arr[0][1]); int[] next2 = kmpNext(arr[1][1]); int[] next3 = kmpNext(arr[2][1]); System.out.println(kmpSeek(arr[0][0], arr[0][1], next1) +1); //加1是因为下标是从0开始的并且返回的是-1 System.out.println(kmpSeek(arr[1][0], arr[1][1], next2) +1); System.out.println(kmpSeek(arr[2][0], arr[2][1], next2) +1); } // 查找匹配字符串 public static int kmpSeek(String str1,String str2,int[] next) { for (int i = 0,j = 0; i < str1.length(); i++) { while(j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j-1]; } if(str1.charAt(i) == str2.charAt(j)) { j++; } if(j == str2.length()) { return i - j + 1; } } return -1; } // 获取str2的部分匹配值 public static int[] kmpNext(String str2) { // 创建一个数组保存部分匹配值 int[] next = new int[str2.length()]; next[0] = 0; for (int i = 1,j = 0; i < str2.length(); i++) { while(j > 0 && str2.charAt(i) != str2.charAt(j)) { j = next[j-1]; } if(str2.charAt(i) == str2.charAt(j)) { // 满足时部分匹配值加1 j++; } next[i] = j; } return next; } } |
9.9 分
5 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复