ITKeyword,专注技术干货聚合推荐

注册 | 登录

【数据结构与算法】字符串匹配KMP算法

benbmw2008 分享于 2014-09-03

推荐:数据结构 KMP算法代码

//匹配字符串模式值  void getFail(char P[],int f[]) { int m=strlen(P); f[0]=0; f[1]=0; for(int i=1;i<m;i++) { int j=f[i]; while(j&&P[i]!=P[j])  j=f[j];

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

首先需要了解一下BF暴力匹配算法,这个算法为每一个串设置一个指针,然后两个指针同时后移,出现不匹配的情况后,主串指针回到开始后移之前的位置的下一位,模式串指针回到最开始。

对比一下KMP算法,同样是设置两个指针,然后两个指针同时后移,出现不匹配的情况后,主串指针不变,模式串指针回溯一定的距离。具体模式串指针回溯多少,是第一次看KMP算法的人比较难以理解的,其实仔细想想,模式串的前缀和后缀其实也是在做匹配,当P[K]!=P[J]时就是失配,那么前缀的指针就需要回溯,所以后k=next[k]。

推荐:KMP算法---字符串匹配

算法细节详见点击打开链接和点击打开链接 #include <stdio.h>#include <stdlib.h>#define N 7#define M 15void showpset(int* a);void cal_pset(char*

  • 代码实现

/**
 * 源码名称:KMP.java 
 * 日期:2014-09-03 
 * 程序功能:KMP算法 
 * 版权:CopyRight@A2BGeek 
 * 作者:A2BGeek
 */
public class KMP {
	public int[] getNext(String in) {
		int[] next = new int[in.length()];
		int j = 0;
		int k = -1;
		next[j] = k;
		while (j < next.length - 1) {
			if (k == -1 || in.charAt(k) == in.charAt(j)) {
				j++;
				k++;
				next[j] = k;
			} else {
				k = next[k];
			}
		}
		for(int i : next) {
			System.out.print(i + " ");
		}
		System.out.println();
		return next;
	}

	public int kmp(String s, String p) {
		int i = 0;
		int j = 0;
		int[] next = getNext(p);
		while (i < s.length() && j < p.length()) {
			if (j == -1 || s.charAt(i) == p.charAt(j)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		if (j == p.length()) {
			return 1;
		} else {
			return -1;
		}
	}

	public static void main(String[] args) {
		KMP kmp = new KMP();
		String s = "acbfdfjkdhg";
		String p = "dfdj";
		System.out.println(kmp.kmp(s, p));
	}
}


推荐:【数据结构与算法】模式匹配——从BF算法到KMP算法(附完整源码)

转载请注明处处:http://blog.csdn.net/ns_code/article/details/19286279 模式匹配     子串的定位操作通常称为串的模式匹配。模式匹配的应用很常见,比如在文

首先需要了解一下BF暴力匹配算法,这个算法为每一个串设置一个指针,然后两个指针同时后移,出现不匹配的情况后,主串指针回到开始后移之前的位置的下一位,模式串指针回到最开始。 对比一下KMP

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。