rk算法进行字符串匹配

❶ 字符串匹配算法是怎么算的

这是一个毕业老师出的字符串的算法的题目！这是答案 可以参考一下！ boyermoore算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 声明： // 该段代码只是BoyerMoore(名字也许不准确) 的基本思想，当 // 然不是最优的，具体完善工作就留给你自己乐！嘻嘻。 // 该算法的本质就是从字符串的右端而不是左端开始比较，这 // 样，当查询不匹配时才有可能直接跃过多个字符（最多可以跃过 // strlen(sFind)个字符）， 如果最右边的字符匹配则回溯。比如： // // pain // ^ 这是第一次比较n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 这是第二次比较，好爽呀！ // The rain in SpainThe rain in Spain // // 当然，这样比较会产生一些问题，比如： // // pain // ^ （图1） // The rain in SpainThe rain in Spain // // 如果比较到这儿，大家都会看到，只需再向后移到两个字符 // 就匹配成功了，但如果接下去还按上面的方法跳strlen( sFind)的 // 话，就会错过一次匹配！！！！！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎么办？当然可以解决！大家回头看图1，当时a是pain的子 // 串，说明有可能在不移动strlen(sFind) 的跨度就匹配成功，那就 // 人为地给它匹配成功的机会嘛！串一下pain串， 直接让两个a对齐 // 再做比较！呵呵，如果要比较的字符不是pain的子串，当然就可 // 以直接跨过strlen(sFind)个字符了！ 不知我说明白没？ // // // 查询串的长度 int nLenOfFind = lstrlen(sFind); // 被查询串的长度 int nLenOfSrc = lstrlen(sSrc); // 指向查询串最后一个字符的指针 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查询串最后一个字符的指针 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比较过程中要用到的两个指针 TCHAR * pSrc = sSrc; TCHAR * pFind; // 总不能一直让它比较到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc <= pEndOfSrc ) { // 每次匹配都是从右向左，这是本算法的核心。 pFind = pEndOfFind; // 如果比较不成功，被查询串指针将向右串的字符数 int nMoveRightSrc; // 比较被查询串的当前字符是否和查询串的最右边字 // 符匹配，如果匹配则回溯比较，如果全匹配了，该 // 干什么，我就不用说了吧？:-) while ( pFind >= sFind ) { // TNND，白废功夫比了！看看需要向右移动几个 // 字符吧（如果说从右到左是本算法的核心，则 // 判断向右移几个字符则是本算法的技巧）。 if ( *pSrc != *pFind ) { // 被查询串的当前字符是否在查询串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 没在，直接移lstrlen(sFind)个字符 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一个！接着向左回溯... pFind --; pSrc --; } // 如果在上面的while循环里每一次比较都匹配了 // 那就对了呗！告诉用户找到了 if ( pFind < sFind ) return ( pSrc + 1 ); // 没匹配成功，nMoveRightSrc上面已经算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序运行到这儿肯定是没指望了！ return NULL; } 行了，函数写完了，我们可以试一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("没找到"); } //另外一个 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }

❷ 题目：KMP算法的实现 内容： 实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较

shit

❸ 字符串匹配的传统算法

传统的匹配算法
串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。串匹配问题的研究存在理论研究和实际应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而开发人员只追求实际应用中尽可能快的算法。两者之间从不注意对方在干什么。将理论研究和实际应用结合的算法(如BNDM算法)只是近年才出现。在实际应用中常常很难找到适合需求的算法——这样的算法实际上是存在的，但是只有资深专家才比较了解。考虑如下情况，一位软件开发人员，或者一位计算生物学家，或者一位研究人员，又或者一位学生，对字符串匹配领域并没有深入了解，可是现在需要处理一个文本搜索问题。那些汗牛充栋的书籍使得阅读者淹没在各种匹配算法的海洋中，却没有足够的知识选择最适用的算法。最后，常常导致这样的局面：选择一种最简单的算法加以实现。这往往导致很差的性能，从而影响整个开发系统的质量。更糟糕的是，选择了一个理论上看起来很漂亮的算法，并且花费了大量精力去实现。结果，却发现实际效果和一个简单算法差不多，甚至还不如简单算法。因此，应该选用一种“实用”算法，即在实际应用中性能较好，并且一个普通程序员能在几小时内完成算法的实现代码。另外，在字符串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。
传统的串匹配算法可以概括为前缀搜索、后缀搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。

❹ kmp算法的d函数

functiond:integer;beginforx∈∑dod(x)=mforj=m-1downto1doifd(w[j])=md(w[j]):=m-jendforendxi+1=ord(ti+1）dm-1+ord(ti+2）dm-2+…+ord(ti+m)=(xi-ord(ti)dm-1）.d+ord(ti+m)因此有 h(xi+1）=((h(xi)-x·ord(ti））·d+ord(ti+m)mod q ，i=1,2，……，n-m
这里x是一常数，x=dm-1mod q。这就是计算每一长度为m的字符段的散列函数值的递推公式。RK串匹配算法由算法1.5给出。

❺ 字符串匹配算法的基本思想是什么

现在最常用的此类算法是改进的KMP算法。/*Name: KMP算法演示Copyright: http://kapinter.spaces.msn.comAuthor: kapinterData: 08-07-06 20:17Description: 串的模式匹配的朴素算法是O(N^2)的, 可以利用KMP(由D.E.Knuth, J.H.Morris, V.R.Pratt提出)算法改进至线性的算法. KMP算法与朴素算法的不同在于处理"失配"情况. 不同于将指针完全回溯, KMP算法先根据已经部分匹配的信息, 将匹配的指针跳过不必匹配的位置.*/#include <iostream.h>#include <string.h>#include <iomanip.h>int Index(char *, char *);int KMP(char *, char *);int main(){char s[256] = "abcabaabcaccaaaabn";char *t[3] = {"abaabcac","aaaab","safasasf"};for (int i=0; i<3; i++) {cout<<"穷举的模式匹配: "<<Index(s, t[i])<<endl;cout<<"KMP算法: "<<KMP(s, t[i])<<endl;cout<<endl;}return 0;}int Index(char *s, char *t){int i = 0;int j = 0;int ls = strlen(s);int lt = strlen(t);while (i<ls && j<lt){if (s[i] == t[j]) {i++;j++;}else {i = i - j + 1;j = 0;}}if (j >= lt) {return (i - lt);}else {return -1;}}int KMP(char *s, char *t){void GetNext(char *, int, int *);int *next = new int[strlen(t)];int lt = strlen(t);int ls = strlen(s);int i, j;GetNext(t, lt, next);i = j = 0;while (i<ls && j<lt){if (j==-1 || s[i]==t[j]) {i++;j++;}else {j = next[j];}}if (j >= lt) {return (i - lt);}else {return -1;}}void GetNext(char *t, int lt, int *next){int i, j;if (lt > 0) { next[0] = -1; }j = -1;i = 0;while (i < lt){if (j==-1 || t[i]==t[j]) {i++;j++;if (t[i] == t[j]) {next[i] = next[j];}else {next[i] = j;}}else {j = next[j];}}cout<<"Next 数组: "<<endl;for (i=0; i<lt; i++) cout<<setw(4)<<t[i];cout<<endl;for (i=0; i<lt; i++) cout<<setw(4)<<next[i];cout<<endl;}/*穷举的模式匹配: 3Next 数组:a b a a b c a c-1 0 -1 1 0 2 -1 1KMP算法: 3穷举的模式匹配: 12Next 数组:a a a a b-1 -1 -1 -1 3KMP算法: 12穷举的模式匹配: -1Next 数组:s a f a s a s f-1 0 0 0 -1 0 2 1KMP算法: -1Press any key to continue

❻ 想找一个解决两个字符串匹配程度的算法。

假设string1="abcde",string2="bcd",则分析逻辑如下：
1. 如果string2长于string1，则不匹配
2. 在string1中顺序查匹配string2中第一个字符的字符，
查到后，如果string1余下的字符串长度小于string2的长度，则不匹配
3. 在上述条件满足时，将string1的下一个字符和string2中的第二个字符匹配，以此类推，一旦有一个不匹配，则不匹配。回到第2步，查找下一个和string2首字符一致的字符。
4. 如果string2中的字符全都匹配上，则说明string2中string1中识别出来了。

❼ 关于一个字符串匹配算法

我看了一下代码的，大概觉得它主要实现的功能是查找*y对应字符串中是否有与*x对应的字符串相等的子字符串存在，如果存在则返回该子串第一个字符在*y中的位置。
但是你没有把问题说清楚，比如preBmBc和memcmp这两个函数是在你给的程序中没有定义的，我猜了好久都不能猜出他们确切的用途。我估计你们老师主要也是叫你们实现这两个函数吧。。
如果你能在把问题给得详细的。。我可以继续帮你想想。。

不愧是毕业设计的题目啊，确实有点难度啊。我觉得那个函数不是一个简单的字符串匹配算法，它是一个多重字符串匹配算法。我给你个C语言的例子你参考一下吧。一下两下我也搞不出来了，真不好意思。
boyermoore算法的sample程序

TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind)
{
//
// 声明：
// 该段代码只是BoyerMoore(名字也许不准确)的基本思想，当
// 然不是最优的，具体完善工作就留给你自己乐！嘻嘻。
// 该算法的本质就是从字符串的右端而不是左端开始比较，这
// 样，当查询不匹配时才有可能直接跃过多个字符（最多可以跃过
// strlen(sFind)个字符），如果最右边的字符匹配则回溯。比如：
//
// pain
// ^ 这是第一次比较n和空格比
// The rain in SpainThe rain in Spain
//
// pain
// ^ 这是第二次比较，好爽呀！
// The rain in SpainThe rain in Spain
//
// 当然，这样比较会产生一些问题，比如：
//
// pain
// ^ （图1）
// The rain in SpainThe rain in Spain
//
// 如果比较到这儿，大家都会看到，只需再向后移到两个字符
// 就匹配成功了，但如果接下去还按上面的方法跳strlen(sFind)的
// 话，就会错过一次匹配！！！！！
//
// pain
// ^
// The rain in SpainThe rain in Spain
//
// 怎么办？当然可以解决！大家回头看图1，当时a是pain的子
// 串，说明有可能在不移动strlen(sFind)的跨度就匹配成功，那就
// 人为地给它匹配成功的机会嘛！串一下pain串，直接让两个a对齐
// 再做比较！呵呵，如果要比较的字符不是pain的子串，当然就可
// 以直接跨过strlen(sFind)个字符了！不知我说明白没？
//
//

// 查询串的长度
int nLenOfFind = lstrlen(sFind);
// 被查询串的长度
int nLenOfSrc = lstrlen(sSrc);
// 指向查询串最后一个字符的指针
TCHAR * pEndOfFind = sFind + nLenOfFind -1;
// 指向被查询串最后一个字符的指针
TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1;

// 在比较过程中要用到的两个指针
TCHAR * pSrc = sSrc;
TCHAR * pFind;

// 总不能一直让它比较到win.com文件的地址去吧？嘻嘻！
while ( pSrc <= pEndOfSrc ) {

// 每次匹配都是从右向左，这是本算法的核心。
pFind = pEndOfFind;

// 如果比较不成功，被查询串指针将向右串的字符数
int nMoveRightSrc;

// 比较被查询串的当前字符是否和查询串的最右边字
// 符匹配，如果匹配则回溯比较，如果全匹配了，该
// 干什么，我就不用说了吧？:-)
while ( pFind >= sFind ) {

// TNND，白废功夫比了！看看需要向右移动几个
// 字符吧（如果说从右到左是本算法的核心，则
// 判断向右移几个字符则是本算法的技巧）。
if ( *pSrc != *pFind ) {

// 被查询串的当前字符是否在查询串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 没在，直接移lstrlen(sFind)个字符
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;

break;
}

// 哈！又匹配成功了一个！接着向左回溯...
pFind --;
pSrc --;
}

// 如果在上面的while循环里每一次比较都匹配了
// 那就对了呗！告诉用户找到了
if ( pFind < sFind )
return ( pSrc + 1 );

// 没匹配成功，nMoveRightSrc上面已经算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}

// 程序运行到这儿肯定是没指望了！
return NULL;
}

行了，函数写完了，我们可以试一下了！

void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";

TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("没找到");
}

//另外一个
void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}

void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];

/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}

❽ 高分求写r-连续位匹配算法的程序

#include <stdio.h>

#define MATCH 1
#define NOMATCH 0
#define ERROR -1

int main (void)
{
int nMatch;

nMatch = r_contiguousbits("100100", "100001", 3);

if(MATCH == nMatch)
printf("Match\n");
else if(NOMATCH == nMatch)
printf("NOMATCH\n");
else
printf("Error\n");

return 0;
}

int r_contiguousbits(char s1[],char s2[],const int r) /*定义匹配函数*/
{
int nIndex = 0;
int nIndex2 = 0;
int nMatch = 0;

if( r <= 0)
return ERROR;

for(nIndex = 0; nIndex < strlen(s1); nIndex++)
{
for(nIndex2 = 0; nIndex2 < strlen(s2) - r; nIndex2++)
{
for(nMatch = 0; nMatch < r; nMatch++)
{
if(s1[nIndex + nMatch] != s2[nIndex2 + nMatch])
break;
}

if(nMatch == r)
return MATCH;
}
}

return NOMATCH;
}
/* 兄弟,这可花了我10分钟的时间在linux下编写的喔 , 答案满意的话请...不够好的话请追问&_& */

❾ kmp算法的RK串匹配

programRK;begin{计算x,x:=d↑（m-1）modq}x=1fori=1tom-1dox=（32*x)modq{计算模式W的散列函数值}s=0fori=1tomdos=((s*32）+ord(w[i]))modq{计算正文T的第一个长度为m的字符段的散列函数值}t=0fori=1tomdot=(t*32+ord(w[i]))modq{如果正文的第一个长度为m的字符段和模式有相同的散列函数值，则进行匹配检查.否则，以及在匹配检查失败情况下，继续计算下一个字符段的散列函数值}i=1whilei<=n-mdoifs=t{进行匹配检查}k=1j=iwhile(t[j]=w[k])and(k<=m)doj=j+1k=k+1endwhileifi<n-m{计算下一字符段的散列函数值}t=((t-x*ord(t[i]))*32+ord(t[i+m]))modqi=i+1endifendifendwhilereturn“FAILURE”end显然，如果不计执行匹配检查的时间，则RK算法的剩余部分执行时间是Θ（m+n)。不过，如果计及执行匹配检查的时间，则在理论上，RK算法需要时耗Θ（mn）。但是，我们总可设法取q适当大，使得mod函数在计算机中仍可执行而冲突（即不同的字符串具有相同的散列值）又极小可能发生，而使算法的实际执行时间只需Θ（m+n）。
BM算法
BM算法和KMP算法的差别是对模式串的扫描方式自左至右变成自右至左。另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式中没有的字符时就可以将模式大幅度滑过正文。
BM算法的关键是根据给定的模式W[1,m]，，定义一个函数d: x->{1,2，…，m},这里x∈∑。函数d给出了正文中可能出现的字符在模式中的位置。