`

算法系列-字符串匹配-rabin-karp算法

阅读更多

ACM-1381题目-Crazy Search

 

方法

 写道
模式字符串进行一个预处理,并mod,主字符串进行逐个进行简单的hash映射,然后mod比较

 

 写道
比如:子串“421″和源串”4234212456″

首先把423对某个质数取模,比如7,把模值和421对7取模的值进行对比。如果相同,则再用朴素算法逐字符对比,如果不同,把423变成234.可以通过(423-400)*10+4=234计算。其实对于任何位数的xyz(具体xyz是几位,要看子串的长度)都可以划分成(xyz-x*100)*10+m

其中m表示父串的下一位。这里的100是以子串长度为3来作比较的. 其中如果换成字符的话应该就是26了。

 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author frank.lv
 *
 */
public class CS {
        //开多少空间要看情况,不能太小
	private boolean[] hash = new boolean[160000];
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		CS cs = new CS();
		
		while(in.hasNext()) {
			int len = in.nextInt();
			int nc = in.nextInt();
			String s = in.next();
			System.out.println(cs.rabin_karp(nc, len, s));
			
		}

	}
	
	/**
	 * @param nc 字母表的大小
	 * @param len 子串的长度
	 * @param s 源字符串
	 * @return
	 */
	private Integer rabin_karp(int nc, int len, String s) {
		int ht = 0;
		int step = 1;
		int ans = 1;
		int sourceLen = s.length();
		int key = 0;
		//字符分配码表
		Map<Character, Integer> wordMap = new HashMap<Character, Integer>();
		
		//step = NC * (len - 1)
		for(int i =1;i<len;i++) {
			step *= nc;
		}
		//分配字母表
		for (int i = 0;; i++) {
			if(!wordMap.containsKey(s.charAt(i))) {
				wordMap.put(s.charAt(i), ++key);
			}
			if(key == nc)
				break;
		}
		//算出第一个子串的HASH值
		for(int i =0;i<len;i++) {
			ht = nc * ht + wordMap.get(s.charAt(i));
		}
		hash[ht] = true;
		
		//RK算法核心
		for(int i = 0; i < sourceLen - len; i++) {
//朴素算法
//4234212456 中 423->234
//nc * ((ht['423'] - 4 * step[100])) + '4'
			ht = nc * (ht - (wordMap.get(s.charAt(i))) * step) + wordMap.get(s.charAt(i + len));
			if(!hash[ht]) {
				hash[ht] = true;
				ans ++;
			}
		}
		
		return ans;
	}

}

 

 

 

参考

http://www.yqshare.com/rabin-karp-and-crazy-search.html

分享到:
评论

相关推荐

    使用模运算改进的字符串匹配Rabin-Karp算法

    **字符串匹配Rabin-Karp算法**是一种在文本中查找子串出现位置的高效算法,它由Rabin和Karp在1987年提出。在传统的字符串匹配算法中,如朴素算法,每次比较一个字符,如果发现不匹配则需要从头开始检查下一个位置,...

    单模式匹配算法 Rabin-Karp

    单模式匹配算法是计算机科学中用于在文本串中查找子串的一种高效方法,Rabin-Karp算法便是其中一种。该算法由Michael O. Rabin和Donald E. Karp于1987年提出,它的主要特点是利用了哈希函数来快速比较文本串中的子串...

    论文研究-支持模式串动态更新的多模式匹配Karp-Rabin算法.pdf

    通过改进Karp-Rabin 算法,实现了多模式字符串匹配技术,实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进,使其在高并发情况下能够支持模式串动态增删功能。实验表明该...

    实验三,微机软件实验3-字符串匹配实验 (2).rar

    4. **Rabin-Karp算法**:该算法使用哈希函数来快速比较子串,通过计算子串的哈希值来减少比较次数。当哈希值匹配时,再进行精确的字符对齐确认。尽管这种方法在最坏情况下可能效率较低,但在大多数情况下,它能显著...

    Rabin-Karp字符串搜索算法介绍和java代码实现

    Rabin-Karp 字符串搜索算法是基于哈希的字符串匹配算法,用于在一个文本中查找一个模式字符串的出现。下面是该算法的概念、特点、优缺点、适用场景和 Java 代码实现。 概念:Rabin-Karp 字符串搜索算法是一种基于...

    C#,字符串匹配(模式搜索)RK(Rabin Karp)算法的源代码

    Rabin-Karp算法,是由M.O.Rabin和R.A.Karp设计实现的一种基于移动散列值的字符串匹配算法。 通常基于散列值的字符串匹配方法:(1)首先计算模式字符串的散列函数;(2)然后利用相同的散列函数计算文本中所有可能...

    各种字符串匹配算法--BM,KMP等

    除了BM和KMP,还有许多其他的字符串匹配算法,如Boyer-Moore-Horspool算法(改进的BM),Rabin-Karp算法(使用哈希函数进行匹配),Sunday算法,以及AC自动机(Aho-Corasick算法)等。这些算法各有优缺点,适用于...

    字符串处理- 单模式匹配- 朴素的字符串匹配算法(BF 算法).rar

    这里我们关注的是一个基础且重要的算法——朴素的字符串匹配算法,也称为BF算法(Brute Force 算法)。 BF算法由D.E.Knuth和J.H.Morris以及V.R.Pratt分别独立提出,因此也被称为KMP算法的前身。它的主要思想是通过...

    PDF电子书《柔性字符串匹配》

    这里可以采用KMP算法或者Rabin-Karp算法来进行高效的字符串匹配,确保检索速度足够快。 #### 4.2 生物信息学中的应用 在基因测序中,需要将新的基因序列与已知数据库中的序列进行比对。这里可以使用后缀树或AC...

    字符串匹配算法之Horspool算法

    当模式串较短或模式串中字符分布较为均匀时,其搜索效率可能不如其他算法如KMP算法或Rabin-Karp算法。此外,对于包含大量随机字符的文本,Horspool算法的平均搜索速度可能接近于O(n),但在最坏情况下仍可能退化为O...

    C++ 字符串匹配

    除了 Brute Force 算法外,还有许多其他的字符串匹配算法,如 Knuth-Morris-Pratt 算法、Rabin-Karp 算法、Boyer-Moore 算法等。 * Knuth-Morris-Pratt 算法是基于 Brute Force 算法的优化版本,它使用一个预处理的...

    字符串匹配算法小集(英文)

    本文档提供了一系列共35种不同的字符串匹配算法,这些算法在英文环境下被广泛讨论和应用。通过对这些算法进行详细的解析,我们可以更好地理解每种算法的特点、应用场景以及其实现方式。 #### 二、概述 在计算机...

    热-KMP算法:字符串匹配的高效利器

    除了KMP算法,还有其他字符串匹配算法,如Boyer-Moore算法、Rabin-Karp算法等。它们各有特点,适用于不同的场景。比如Boyer-Moore算法利用坏字符规则和好后缀规则,比KMP更高效但实现相对复杂;Rabin-Karp算法则基于...

    字符串匹配算法C代码实现

    Rabin-Karp算法是基于哈希函数的字符串匹配算法。它首先计算模式串和主串各窗口的哈希值,然后通过比较哈希值来快速判断两个字符串是否可能相等。如果哈希值不同,则可以直接排除匹配;若相同,则需进一步检查具体...

    32丨字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?1

    本节主要讨论了两种基本的字符串匹配算法:BF 算法(Brute Force 算法,又称暴力匹配算法)和 RK 算法(Rabin-Karp 算法),并探讨了如何利用哈希算法提高匹配效率。 BF 算法是最直观的字符串匹配方法,它通过逐一...

    ACM-字符串处理专练

    3. **字符串匹配**:涉及到模式匹配问题,比如正则表达式匹配,Trie树(字典树)或Aho-Corasick自动机常用于快速查找多个模式。 4. **字符串反转**:这是一个常见的字符串操作,可以使用双指针技术或者栈来实现。 ...

    字符串匹配

    2. **预处理匹配**,包括KMP(Knuth-Morris-Pratt)算法、Boyer-Moore算法和Rabin-Karp算法等,它们通过预处理模式字符串来减少不必要的字符比较。例如,KMP算法创建了部分匹配表,使得在不匹配时可以跳过已匹配的...

    Karp算法 c++实现

    运用Karp算法实现字符串匹配的c++程序

    精选_毕业设计_基于C#实现并对比三种基本的字符串匹配算法-RK算法-KMP算法-朴素算法_完整源码

    在IT领域,字符串匹配是计算机科学中的一个基础且重要的问题,尤其在文本处理、搜索算法、数据挖掘等应用中有着广泛的应用。本毕业设计聚焦于三种经典的字符串匹配算法:RK算法、KMP算法和朴素算法,并用C#编程语言...

    文件中字符串匹配算法C语言版

    顺序匹配是最直观的方法,逐字符比较,而模式匹配算法则更为复杂,如Boyer-Moore算法、KMP算法或Rabin-Karp算法,它们旨在减少不必要的字符比较,提高效率。 在这个C语言实现的版本中,我们可能看到了一个简单的...

Global site tag (gtag.js) - Google Analytics