KMP算法

简介: <p>KMP为的是解决2字符串匹配问题的算法,检查一个字符串是否为另一个的子串,sub = "abc" , str = "aabcd" ,str里包含了一个sub,KMP算法可以以O(M+N)的复杂度找到子串在str的位置。</p> <p>那代码怎么实现呢:</p> <p></p><pre code_snippet_id="1637751" snippet_file_name="bl

KMP为的是解决2字符串匹配问题的算法,检查一个字符串是否为另一个的子串,sub = "abc" , str = "aabcd" ,str里包含了一个sub,KMP算法可以以O(M+N)的复杂度找到子串在str的位置。

那代码怎么实现呢:

public class Kmp {
	
	public static void main(String[] args) {
		 String str = "abbabbbbcab";   
	     String sub = "bbcab"; 
	     char[] s=str.toCharArray();
	     char[] t=sub.toCharArray();
	    System.out.println("s包含t的位置"+KMP_Index(s, t)); 
	}
	
	/**
	 * @param s
	 * @param t
	 * @return 匹配成功 返回模式串在主串中的头下标,匹配失败返回-1  
	 */
	 public static int KMP_Index(char[] s, char[] t) {  
	        int[] next = next(t);  
	        int i = 0;  
	        int j = 0;  
	        while (i <= s.length - 1 && j <= t.length - 1) {  
	            if (j == -1 || s[i] == t[j]) {  
	                i++;  
	                j++;  
	            } else {  
	                j = next[j];  
	            }  
	        } 
	        
	        if (j < t.length) {  
	            return -1;  
	        } else {
	        	return i - t.length; 
	        } 
	    }  
	
	public static int[] next(char[] t) {  
        int[] next = new int[t.length];  
        next[0] = -1;  
        int i = 0;  
        int j = -1;  
        while (i < t.length - 1) {  
            if (j == -1 || t[i] == t[j]) {  
                i++;  
                j++;  
                if (t[i] != t[j]) {  
                    next[i] = j;  
                } else {  
                    next[i] = next[j];  
                }  
            } else {  
                j = next[j];  
            }  
        }  
        return next;  
    }  
	
}


目录
相关文章
|
4月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
3月前
|
机器学习/深度学习 监控 算法
局域网行为监控软件 C# 多线程数据包捕获算法:基于 KMP 模式匹配的内容分析优化方案探索
本文探讨了一种结合KMP算法的多线程数据包捕获与分析方案,用于局域网行为监控。通过C#实现,该系统可高效检测敏感内容、管理URL访问、分析协议及审计日志。实验表明,相较于传统算法,KMP在处理大规模网络流量时效率显著提升。未来可在算法优化、多模式匹配及机器学习等领域进一步研究。
93 0
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
314 3
|
11月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
158 0
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
11月前
|
算法
KMP算法
KMP算法
114 0
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
316 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
算法
KMP算法
KMP算法
96 0
|
算法 搜索推荐 程序员
第六十三练 字符串匹配 - KMP算法
第六十三练 字符串匹配 - KMP算法
87 2
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用

热门文章

最新文章