暴力字符串匹配算法

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

这是一个毕业老师出的字符串的算法的题目！这是答案 可以参考一下！ 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); } }

❷ BF的五种意思是什么

1、BF，网络流行词，即boyfriend的简称，就是男朋友的意思。该词是相对于GF（girl friend）而言的。

2、BF，波束成形，是张韵聪博士在2004年IEEE期刊曾提出的一种编程算法。

3、BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

4、BF，是BUTFIRST的缩写，目的是去掉第一个（在字符串、数字、数组）中。

5、BF：Brainfuck是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。由于fuck在英语中是脏话，这种语言有时被称为brainf*ck或brainf***，甚至被简称为BF。

❸ 给出字符串在KMP算法中的Next数组

逐个查找对称串。

只要循环遍历这个子串，分别看前1个字符，前2个字符，3个... i个 最后到15个。

第1个a无对称，所以对称程度0

前两个ag无对称，所以也是0

依次类推前面0-4都一样是0

最后一个是0～3都一样是0

前缀next数组的求解算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字符串长度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推

while( Pattern[i] != Pattern[k] && k!=0 )

k=prefix[k-1]; //继续递归

if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

}

}

(3)暴力字符串匹配算法扩展阅读：

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

❹ kmp算法的基本思想

主串：a b a c a a b a c a b a c a b a a b b，下文中我们称作T
模式串：a b a c a b，下文中我们称作W
在暴力字符串匹配过程中，我们会从T[0] 跟 W[0] 匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。
然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
在第一次匹配过程中
T: a b a c a a b a c a b a c a b a a b b
W: a b a c ab
在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：
T: a b a c aab a c a b a c a b a a b b
W: a b a c ab
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如： j012345W[j]abacabF(j)001012当W[j]与T[i]不匹配的时候，设置j = F(j-1)
文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。
以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。

❺ 字符串匹配算法

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);
}
}

❻ bf算法是什么

BF算法，即暴力(Brute Force)算法。

是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

如果一个多位数并且包含以上所有可能字符的密码，其组合方法一定多的惊人，且每增加一位数，密码组合数量会以数十倍指数成长，破译的时间也会更长，有时可能长达数十年（即便考虑电脑性能依摩尔定律的进步），甚至更久。

由于穷举法破解所消耗的时间不小于完成破解所需要的多项式时间，故从密码学角度考虑，不认为穷举法是有效的破解方法。

字典攻击

破译一个相当长度并且包含各种可能字符的密码所耗费的时间相当长，其中一个解决办法就是运用字典。所谓“字典攻击”就是使用预先制作好的清单，例如：英文单字、生日的数字组合、以及各种常被使用的密码，等等，利用一般人习惯设置过短或过于简单的密码进行破译，很大程度上缩短了破译时间。

防护手段

最重要的手段是在构建系统时要将系统设计目标定为即便受到暴力破解的攻击也难以被攻破。以下列举了一些常用的防护手段：

1、增加密码的长度与复杂度。

2、在系统中限制密码尝试的次数。

3、密码验证时，将验证结果不是立即返回而是延时若干秒后返回。

4、限制允许发起请求的客户端的范围。

5、禁止密码输入频率过高的请求。

6、将密码设置为类似安全令牌那样每隔一定时间就发生变化的形式。

7、当同一来源的密码输入出错次数超过一定阈值，立即通过邮件或短信等方式通知系统管理员。

8、人为监视系统，确认有无异常的密码试错。

9、使用双因子认证，例如用户登录账号密码时，系统同时发送短信到用户的手机，用户需输入短信内的认证码。

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

现在最常用的此类算法是改进的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

❽ 字符串匹配算法，最快的是哪种

目前在我遇到的字符串匹配算法中，最快的应该是sunday算法了。。
(BF、KMP、BM、sunday)

❾ 最容易理解，容易学的的字符串匹配算法

最简单的是暴力匹配 叫什么我忘了 就是双重for循环 复杂度是n1*n2

其次是Sunday算法 具体过程自己搜吧 也不难 算是剑走偏锋的 而且它的速度一般是最快的 复杂度 n1+n2

然后是kmp算法 纯论速度它还不如Sunday 算法 而且也比较难理解 但是它对于后面的一些其他的学习是有必要的 复杂度 n1+n2