高效字符串查找算法之KMP算法的java实现

╰半夏微凉° 2023-03-14 10:44 5阅读 0赞

## 源代码 ##

public class KMP { 
    
    	public static void main(String[] args) { 
    		String mainStr = "ABCDAB ABCDABDOIJEF";
    		String subStr = "ABCDABD";
    
    		System.out.println(kmpSearch(mainStr,subStr,0));
    	}
    	
    	public static int kmpSearch(String str1, String str2, int pos) { 
    		int[] next = getNext(str2);
    		
    		for(int i=pos,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-str2.length()+1;
    			}
    		}
    		
    		return -1;
    	}
    	
    	public static int[] getNext(String str) { 
    		int[] next = new int[str.length()];
    		
    		next[0] = 0;
    		for(int i=1,j=0; i<str.length(); i++) { 
    			while(j > 0 && str.charAt(i) != str.charAt(j)) { 
    				j = next[j-1];
    			}
    			
    			if(str.charAt(i) == str.charAt(j)) { 
    				j++;
    			}
    
    			next[i] = j;
    			
    		}
    		return next;
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java实现之KMP算法

目录一.字符串匹配问题二.暴力匹配算法 1.思路分析 2.代码实现三.KMP算法的 1.基本介绍 2.思路分析 3.代码实现 -------------

àì夳堔傛蜴生んèń/ 2024年04月01日 17:58/ 0 赞/ 65 阅读

相关高效字符串查找算法之KMP算法的java实现

源代码 public class KMP { public static void main(String[] args) {

╰半夏微凉°/ 2023年03月14日 10:44/ 0 赞/ 6 阅读

相关字符串匹配算法之KMP

目录需求基础知识逻辑解析源码实现需求先简单描述溪源曾经遇到的需求：需求一：项目结果文件中实验结论可能会存在未知类型、转换错

绝地灬酷狼/ 2023年03月01日 08:37/ 0 赞/ 2 阅读

相关字符串查找，KMP算法讲解

KMP 时间复杂度： O(n+m) 核心点；最长公共前后缀长度数组:next 若p\[i-1\]=p\[next\[i-1\]\],则 next\[i\] =

野性酷女/ 2023年01月02日 14:27/ 0 赞/ 252 阅读

相关算法——字符串匹配之KMP算法

前言前面博文分别介绍了字符串匹配算法《[朴素算法][Link 1]》、《[Rabin-Karp][][算法][Rabin-Karp]》和《[有限自动机算法][Link

柔光的暖阳◎/ 2022年08月13日 00:52/ 0 赞/ 223 阅读

相关算法字符串匹配之朴素算法和KMP算法及JAVA代码实现

暴力匹配算法假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串S匹配到 i

以你之姓@/ 2022年06月15日 11:55/ 0 赞/ 177 阅读

相关 python算法-字符串查找KMP算法

问题：对于一个给定非空的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，

刺骨的言语ヽ痛彻心扉/ 2022年05月30日 22:10/ 0 赞/ 206 阅读

相关字符串匹配算法之KMP

给定两个字符串S、P，如何判断S中包含P？(假设S为较长字符串，要求P中字符在S中要连续出现) 这就是经典的字符串匹配问题。暴力匹配略去不说，一种较好的解法就是KMP。对于一

た入场券/ 2022年01月05日 10:47/ 0 赞/ 301 阅读

相关字符串之KMP算法

一、介绍　　KMP算法全称Knuth-Morris-Pratt算法，是一种字符串匹配算法，常规字符匹配是每次移动一位，复杂度O(mn)；而KMP算法复杂度O(m+n)。

谁借莪１个温暖的怀抱￠/ 2021年09月11日 01:54/ 0 赞/ 410 阅读

相关 KMP算法实现字符串匹配

一需求 1 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"。 2 现在要判断 str1 是否含

以你之姓@/ 2021年07月24日 23:06/ 0 赞/ 446 阅读