KMA算法实现

心已赠人 2022-06-15 03:23 87阅读 0赞

# KMA算法实现 #

/**
     * KMA字符串匹配算法
     * @author KeXin
     *
     */
    public class Test{
    	public static int[] ComputePrefix(String p){
    		char[] P = p.toCharArray();
    		int m = P.length;
    		int[] t = new int[m];
    		t[0] =  0;
    		int k = 0;
    		for(int q = 1;q<m;q++){
    			while(k>0&&P[k]!=P[q])
    				k = t[k];
    			if(P[k]==P[q])
    				k = k+1;
    			t[q] = k;
    		}
    		
    		return t;
    	}
    	public static void KMA(String t,String p){
    		char[] P = p.toCharArray();
    		char[] T = t.toCharArray();
    		int n = T.length;
    		int m = P.length;
    		int[] pai = ComputePrefix(p);
    		for(int i = 0;i<m;i++)
    			System.out.print(pai[i]+"\t");
    		System.out.println();
    		int q = 0;
    		for(int i = 0;i<n;i++){
    			while(q>0&&P[q]!=T[i])
    				q = pai[q];
    			if(P[q]==T[i])
    				q = q+1;
    			if(q==m){
    				System.out.println("Matches in "+(i-m+1));
    				q = 0;
    			}
    		}
    	}
    	public static void main(String[] args) {
    //		String p = "ababaca";
    //		String t = "aaababacaaaababacab";
    		String p = "ab";
    		String t = "abcabcabdabeba";
    		KMA(t,p);
    	}
    
    }

发表评论取消回复

表情：

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

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

相关阅读

相关实现LRU算法

本文参考Java 的 LinkedHashMap 集合源码数据结构：LinkedHashMap 说明：LinkedHashMap中有个参数 accessOrder ，

た入场券/ 2022年12月30日 01:26/ 0 赞/ 320 阅读

相关 Floyd算法实现(.)

最短路径算法 Floyd算法实现 const int INF = 65535; void GetShortestPath_Floyd(MGraph

缺乏、安全感/ 2022年12月27日 08:41/ 0 赞/ 143 阅读

相关 GC算法实现

在了解了上一章中GC算法的基本概念之后，本章将深入到各GC算法的具体实现中。对大多数JVM来说，一般需要选择两种GC算法，一种用于回收新生代内存区，另一种用于回收老年代内存区域

谁借莪１个温暖的怀抱￠/ 2022年10月01日 09:59/ 0 赞/ 171 阅读

相关贪心算法实现

一. 给出解决文件压缩问题的贪心算法 Algorithm -HUFFMAN 输入: n个字符的集合C=\{c1,c2,…,cn\}和它们的频度\{f(c1),

我就是我/ 2022年07月14日 09:40/ 0 赞/ 222 阅读

相关 kruscal算法实现

达到的 include <iostream> include <algorithm> using namespace std; in

港控/mmm°/ 2022年07月12日 14:00/ 0 赞/ 60 阅读

相关 KMA算法实现

KMA算法实现 / KMA字符串匹配算法 @author KeXin / public class Test

心已赠人/ 2022年06月15日 03:23/ 0 赞/ 88 阅读

相关 AES算法实现

AES算法实现 1）AES：密码学中的高级加密标准（Advanced Encryption Standard，AES），又称Rijndael 加密法，是美国联邦政府采

客官°小女子只卖身不卖艺/ 2022年05月30日 10:39/ 0 赞/ 192 阅读

相关各种算法实现

排序算法 1，冒泡排序（稳定）———时间复杂度O(n^2) 冒泡排序是比较任何两个相邻元素，如果第一个比第二个大就交换两个的位置。那么较大的值就会一点一点移动到后面正确的

水深无声/ 2022年03月09日 10:08/ 0 赞/ 233 阅读

相关 HotSpot算法实现

1.枚举根节点可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中。可达性分析对执行时间的敏感体现在GC停顿上

淡淡的烟草味﹌/ 2022年01月12日 08:35/ 0 赞/ 152 阅读

相关算法-java实现

1. 质因数分解 public static List<Integer> factorize(int n){ List<Integer> f

r囧r小猫/ 2021年12月16日 10:04/ 0 赞/ 242 阅读