匹配检索算法

❶ 匹配算法依据是什么

其主要原理都是切分出单字串，然后和词库进行比对，如果是一个词就记录下来， 否则通过增加或者减少一个单字，继续比较，一直还剩下一个单字则终止，如果该单字串无法切分，则作为未登录处理。

❷ 通讯录拼音搜索模糊匹配的算法问题

我用java写了个简单的，你可以多测试下：

publicstaticvoidmain(String[]args){

		String[]name={"wang","hai","bao"};

		String[]tests={"whb","WaHB","wangHB","HB","wh","whbo","whba"};

		for(Stringstring:tests){
			System.out.println(string+":"+match(name,string));
		}

	}

	publicstaticbooleanmatch(String[]source,Stringinput){

		if(source==null||source.length==0||input==null||input.length()==0){
			returnfalse;
		}

		Stringtemp;

		//统一转小写
		input=input.toLowerCase();

		for(inti=0;i<source.length;i++){

			temp=source[i].toLowerCase();

			if(temp==null||temp.length()==0){
				returnfalse;
			}
			
						//最后一步特殊处理
			if(i==source.length-1){
				if(temp.startsWith(input)){
					returntrue;
				}
			}

			//输入的字符完全匹配到
			if(input.startsWith(temp)){
				//匹配到后生成新的字符串
				input=input.substring(0,input.indexOf(temp));
				//System.out.println("temp:"+temp+"	匹配到后input："+input);
			}

			//首字母匹配到
			elseif(temp.startsWith(input.substring(0,1))){

				input=input.substring(1);
				//System.out.println("temp:"+temp+"	匹配到后input："+input);
			}else{
				returnfalse;
			}

			//表示匹配结束
			if(input.length()==0){
				returntrue;
			}

		}

		returnfalse;
	}

❸ 串模式匹配算法

# include <string.h> # include <stdio.h> # include <stdlib.h> # define OK 1 # define ERROR 0 typedef int Status; //串的定长顺序存储结构 # define MAX_STR_LEN 40 typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度 Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T { int i; if (strlen(chars) > MAX_STR_LEN) { return ERROR; } else { T[0] = strlen(chars); for (i=1; i<=T[0]; ++i) { T[i] = * (chars + i - 1); } return OK; } } //返回串S的元素的个数 int StrLength(SString S) { return S[0]; } //用Sub返回串S的自第pos个字符起长度为len的子串 Status SubString(SString Sub,SString S,int pos,int len) { int i; if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) { return ERROR; } for (i=1; i<=len; ++i) { Sub[i] = S[pos+i-1]; } Sub[0] = len; return OK; } //输出字符串T void StrPrint(SString T) { int i; for (i=1; i<=T[0]; ++i) { printf("%c ",T[i]); } printf("\n"); } //求模式串T的next函数值并存入数组next void get_next(SString T,int next[]) { int i = 1,j = 0; next[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } } //求模式串T的next函数修正值并存入数组nextval void get_nextval(SString T,int nextval[]) { int i = 1,j = 0; nextval[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; if (T[i] != T[j]) { nextval[i] = j; } else { nextval[i] = nextval[j]; } } else { j = nextval[j]; } } } //利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法 //1=<pos=<StrLength(S) int Index_KMP(SString S,SString T,int pos,int next[]) { int i = pos,j = 1; while (i<=S[0] && j<=T[0]) { if (j==0 || S[i]==T[j]) { ++i; ++j; } else { j = next[j]; } } if (j > T[0]) { return i - T[0]; } else { return 0; } } int main(void) { int i,* p; SString s1,s2; StrAssign(s1,"aaabaaaab"); printf("主串为："); StrPrint(s1); StrAssign(s2,"aaaab"); printf("子串为："); StrPrint(s2); p = (int *)malloc((StrLength(s2) + 1) * sizeof(int)); get_next(s2,p); printf("子串的next的数组为："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); i = Index_KMP(s1,s2,1,p); if (i) { printf("主串和子串在第%d个字符处首次匹配\n",i); } else { printf("主串和子串匹配不成功\n"); } get_nextval(s2,p); printf("子串的nextval数组为："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p)); printf("求串s1的从第5个字符起长度为5的子串s2:\n"); SubString(s2,s1,5,5); printf("串s2为:"); StrPrint(s2); return 0; } /* 在vc++6.0中的输出结果： ------------------------ 主串为：a a a b a a a a b 子串为：a a a a b 子串的next的数组为：0 1 2 3 4 主串和子串在第5个字符处首次匹配 子串的nextval数组为：0 0 0 0 4 主串和子串在第5个字符处首次匹配 求串s1的从第5个字符起长度为5的子串s2: 串s2为:a a a a b Press any key to continue ------------------------------ */

❹ 字符串匹配的传统算法

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

❺ bm是什么意思

BM是一种匹配算法。

BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。

BM算法主要思想描述如下：

模式字符串的匹配顺序是从右向左:

1、首先将P和T对齐，即p和t对齐；

2、然后匹配从模式字符串P的最右端字符开始，即判断p[m]和t[m]是否匹配：

如果匹配成功，则向左移动判断p[m-1]和t[m-1]是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。

BM算法的原理：

不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理 P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。

这样，就需要将字串中的所有字符一一比较。Boyer-Moore算法的关键在于，当 P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。

如果最后一个字符未在 P中出现，那么我们可以直接跳过 T的n个字符，比较接下来的n个字符，n为 P的长度（见定义）。

如果最后一个字符出现在 P中，那么跳过的字符数需要进行计算（也就是将 P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。

❻ 字符串匹配算法

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的关键是部分匹配表。理解KMP的主要障碍是没有完全掌握部分匹配表中的值到底意味着什么。试着用最简单的话来解释它们。

这是“abababca”模式的部分匹配表：

现在，为了谈论其含义，我们需要了解正确的前缀和正确的后缀。

字符串中的所有字符，其中一个或多个字符被截断。
“S”，“Sn”，“Sna”和“Snap”都是“Snape”的正确前缀。
截取的范围是从字符串的第一个字符到倒数第二个字符。

字符串中的所有字符，一个或多个字符在开头处截断。
“agrid”，“grid”，“rid”，“id”和“d”都是“Hagrid”的正确后缀。
截取的范围是从字符串的第二个字符到倒数第一个字符。

考虑到这一点，我现在可以给出部分匹配表中值的一句话含义：

现在来分析“abababca”这个模式串：

对“a”分析，只有一个字符串，没有前缀和后缀，故值为0。

对“ab”分析，有一个正确的前缀（“a”）和一个正确的后缀（“b”），前缀和后缀不匹配，故值为0。

对“aba”分析，有两个正确的前缀（“a”和“ab”）和两个正确的后缀（“a”和“ba”）。正确的前缀“ab”与两个正确的后缀中的任何一个都不匹配。但是，正确的前缀“a”与正确的后缀“a”匹配。因此，在这种情况下，匹配正确后缀的最长正确前缀的长度是1。

对四个字符（“abab”）分析，有三个正确的前缀（“a”，“ab”和“aba”）和三个正确的后缀（“b”，“ab”和“bab”）。“ab”在两者中，并且是两个字符长，因此值为2。

对“ababa”分析，有四个正确的前缀（“a”，“ab”，“aba”和“abab”）和四个正确的后缀（“a”，“ba”，“aba”和“baba”）。现在，有两个匹配：“a”和“aba”都是正确的前缀和正确的后缀。由于“aba”比“a”长，所以它获胜，因此值为3。

对“abababc”分析。即使没有列举所有正确的前缀和后缀，显然也不会有任何匹配; 所有后缀都以字母“c”结尾，并且没有前缀与之匹配，因此值为0。

对“abababca”分析，由于它们都以“a”开头和结尾，我们知道它的值至少为1.但是，它就是它的结束点; 在长度为2或更高时，所有后缀都包含ac，而只有最长的前缀（“abababc”）包含“c”。这个七个字符的前缀与七个字符的后缀（“bababca”）不匹配，因此值为1。

当我们找到部分匹配时，我们可以使用部分匹配表中的值来跳过（而不是重做不必要的旧比较）。该公式的工作方式如下：

如果找到长度为partial_match_length的部分匹配table[partial_match_length] > 1，我们可以跳过前面的partial_match_length - table[partial_match_length - 1]字符。

假设我们将“abababca”模式与“bacbababaabcbab”相匹配。这里是我们的部分匹配表，以便于参考：

我们第一次获得部分匹配是在这里：

这是partial_match_length为1. table[partial_match_length - 1]（或table[0]）的值为0，因此我们不会先跳过任何一个。我们得到的下一个部分匹配是：

这是partial_match_length为5. table[partial_match_length - 1]（或table[4]）的值为3.这意味着我们可以跳过前面partial_match_length - table[partial_match_length - 1]（或5 - table[4]或5 - 3或2）字符：

这是partial_match_length 3. table[partial_match_length - 1]（或table[2]）的值是1.这意味着我们可以跳过前面partial_match_length - table[partial_match_length - 1]（或3 - table[2]或3 - 1或2）字符：

❽ 【算法笔记】字符串匹配

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：

主串和模式串：
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m

我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度是 O(n*m)

等价于

比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰
内容来自 http://www.ruanyifeng.com/blog/

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6 - 2 等于4，所以将搜索词向后移动4位。

因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是着名的KMP 算法的 3 到 4 倍。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

未完待续

参考文章：
字符串匹配的Boyer-Moore算法

❾ 什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。