String Matching -- Brute Force + Rabin-Karp + KMP

2024-06-06 09:32

本文主要是介绍String Matching -- Brute Force + Rabin-Karp + KMP,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

String Matching





这个问题已经被做烂了...

下面是C语言实现集合.

http://www-igm.univ-mlv.fr/~lecroq/string/

留个爪~






暴力解法:

     

暴力美啊~

"""
Programmer  :   EOF
Date        :   2015.02.28
Code file   :   nsm.py"""def naive_string_matcher(T, P) :if (T or P) is None :return n = len(T)m = len(P)for s in range(0, n-m+1) :match = Truefor i in range(0, m) :if P[i] is not T[s+i] :match = Falsebreakif match is True :print "Pattern occurs with shift", s#------------ for testing --------------------string1 = "hello goodbye and hello"
string2 = "hello"
naive_string_matcher(string1, string2)



Rabin-Krap :

"""
Programmer  :   EOF
Code date   :   2015.02.28
Code file   :   rkm.py
e-mail      :   jasonleaster@gmail.com"""
def rabin_karp_matcher(T, P, d, q) :n = len(T)m = len(P)h = d**(m-1) % qp = 0t_0 = 0t = [0 for i in range(0, n - m + 1)]# preprosecessingfor i in range(0, m) :p = ( d*p + ord(P[i]) ) % qt[0] = (d*t[0] + ord(T[i])) % q# matchingfor s in range(0, n-m+1) :match = Trueif p is t[s] :for i in range(0, m) :if P[i] is not T[s+i] :match = Falsebreakif match is True :print "Pattern occurs with shift", sif s < n-m :t[s+1] = (d * ( t[s] - ord(T[s]) * h ) + ord(T[s+m]) ) % q#------------ for testing --------------------string1 = "hello goodbye and hello"
string2 = "hello"
rabin_karp_matcher(string1, string2, 10, 13)



KMP:

"""
Programmer  :   EOF
Code date   :   2015.02.28
Code file   :   kmp.py
e-mail      :   jasonleaster@gmail.comCode description    :Here is a implementation of KMP which is a useful
algorithm for string matching."""def kmp_matcher(T, P) :n = len(T)m = len(P)pi = compute_prefix_function(P)q = -1 # number of characters matchedfor i in range(0, n) : # scan the text from left to rightwhile q > 0 and P[q+1] != T[i] :q = pi[q]       # next character doesn't matchif P[q+1] == T[i] :q += 1          # next character matchesif (q+1) == m :         # Is all of P matched ?print "Pattern occurs with shift ", i-mq = pi[q]       # look for the next matchdef compute_prefix_function(P) :m = len(P)pi = [-1 for i in range(0, m)]k = -1 # Attention !for q in range(1, m) :while k > 0 and P[k+1] != P[q] :k = pi[k]if P[k+1] == P[q] :k += 1pi[q] = kreturn pi#-------------for testing----------------------
#string_1 = "hello goodbye and hello"
#string_2 = "hello"
string_1 = "abcabaabcabac"
string_2 = "abaa"
kmp_matcher(string_1, string_2)





PHP神人吐槽KMP




waiting for updates ... ...





这篇关于String Matching -- Brute Force + Rabin-Karp + KMP的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1035724

相关文章

codeforces535D:Tavas and Malekas(KMP)

(i-1 , i)有重合的时候 ,从第i位开始的子串必须是模式串的前缀。 而同时,从第i位开始的子串本来就已经是模式串的后缀了。 typedef long long LL ;const int maxn = 1000008 ;int next[maxn] ;void getnext(char s[]){int len = strlen(s) ;next[0] = -1 ;i

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

hdu2072(string的应用)

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25447    Accepted Submission(s): 5957 Problem Description lily的好朋友xiaoou333最近很空,他

【UVA】10739 - String to Palindrome(动态规划)

比较水的动态规划 dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数 其中删除操作和添加操作本质上是一样的。 三个状态转移方程: dp[i][j] = min(dp[i][j] ,dp[i + 1][j]); dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]); dp[i][j] = min(dp[i][j] ,dp[

理解String的compareTo()方法返回值

compareTo()的返回值是整型,它是先比较对应字符的大小(ASCII码顺序), 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值。 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符作比较, 以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度。 我们可以通过阅读源码加深对compareTo()的理解: comp

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

leetcode#10. Regular Expression Matching

题目 Implement regular expression matching with support for ‘.’ and ‘*’. '.' Matches any single character.'*' Matches zero or more of the preceding element.The matching should cover the entire input

leetcode#541. Reverse String II

题目 Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of

Java中Map取值转String Null值处理

Map<String, Object> 直接取值转String String value = (String)map.get("key") 当map.get(“key”)为Null值时会报错。 使用String类的valueOf静态方法可以解决这个问题 String value = String.valueOf(map.get("key"))