Java实现字符串匹配
JAVA 实现 字符串 匹配
2023-09-14 08:58:13 时间
1 问题描述
给定一个n个字符组成的串(称为文本),一个m(m <= n)的串(称为模式),从文本中寻找匹配模式的子串。
2 解决方案
2.1 蛮力法
package com.liuzhen.chapterThree;
public class BruteForceStringMatch {
//根据文本串N,和模式串M,返回第一个匹配模式串的子串在N中的位置
public static int getStringMatch(int[] N , int[] M){
int n = N.length; //文本串的长度
int m = M.length; //模式串的长度
for(int i = 0;i < n-m;i++){ //最后一轮子串匹配的起始位置是n-m,如果大于n-m一定不会出现匹配子串
int j = 0;
while(j < m && M[j] == N[i+j])
j = j +1;
if(j == m)
return i;
}
return -1;
}
public static void main(String args[]){
int[] N = {1,2,3,2,4,5,6,7,8,9};
int[] M = {6,7,8};
int position = getStringMatch(N,M);
System.out.println("文本串N中第"+position+"位开始,可以寻找一个匹配模式M的子串,该位置字符值为:"+N[position]);
}
}
运行结果:
文本串N中第6位开始,可以寻找一个匹配模式M的子串,该位置字符值为:6
2.2 KMP模式匹配法
package com.liuzhen.practice;
public class Main {
//获取匹配字符串B的next函数值
public int[] getNext(String B) {
char[] arrayB = B.toCharArray();
int[] next = new int[arrayB.length + 1];
int j = 0;
for(int i = 1;i < arrayB.length;i++) {
while(j > 0 && arrayB[i] != arrayB[j])
j = next[j];
if(arrayB[i] == arrayB[j])
j++;
next[i + 1] = j;
}
return next;
}
//输出B在A中出现匹配子串所有情况的第一个位置
public void getKMP(String A, String B) {
int[] next = getNext(B);
char[] arrayA = A.toCharArray();
char[] arrayB = B.toCharArray();
int j = 0;
for(int i = 0;i < arrayA.length;i++) {
while(j > 0 && arrayA[i] != arrayB[j])
j = next[j];
if(arrayA[i] == arrayB[j])
j++;
if(j == arrayB.length) {
System.out.println("开始匹配位置:"+(i - j + 1));
j = 0; //重新开始新的匹配检查
}
}
return;
}
public static void main(String[] args) {
Main test = new Main();
String A = "bbaabbbbbaabbbbaabb";
String B = "bbbaa";
test.getKMP(A, B);
}
}
运行结果:
开始匹配位置:6
开始匹配位置:12
相关文章
- Java实现 LeetCode 792 自定义字符串排序(暴力)
- Java实现 蓝桥杯 算法训练 Airport Configuration
- Java实现 蓝桥杯 算法训练 字符串长度(IO无敌)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 237 删除链表中的节点
- Java实现UVA10131越大越聪明(蓝桥杯每周一题)
- Java实现 LeetCode 123 买卖股票的最佳时机 III(三)
- Java实现 LeetCode 87 扰乱字符串
- Java实现 基础算法 求100以内的质数
- java实现第七届蓝桥杯路径之谜
- java实现第六届蓝桥杯饮料换购
- Java实现第十届蓝桥杯最大降雨量
- Java实现字符串编辑距离
- java实现字符串比较
- java实现子集和问题
- Java实现字符串转换成整数
- Java实现字符串转换成整数
- Java实现字符串的旋转
- Java实现 蓝桥杯VIP 算法提高 字符串比较
- Java实现 蓝桥杯VIP 算法提高 字符串比较
- Java实现 蓝桥杯VIP 算法提高 3-2字符串输入输出函数
- Java实现 蓝桥杯VIP 算法训练 连接字符串
- Java实现 蓝桥杯VIP 算法训练 最长字符串
- Java实现 蓝桥杯VIP 算法训练 最长字符串
- (Java实现) 零件分组
- Atitit 插件机制原理与设计微内核 c# java 的实现attilax总结
- 编程笔试(解析及代码实现):国内各大银行(招商银行/浦发银行等)在线笔试常见题目(猴子吃桃/字符串逆序输出/一段话输出字的个数/单词大小转换等)及其代码实现(Java/Python/C#等)之详细攻略
- java中接口的定义与实现