㈠ 【算法笔记】字符串匹配
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算法
㈡ 求出首次与字符串匹配的起始位置的代码，要在c++里实现的。
1.朴素的模式匹配也叫B-F算法int Find{int i,j;for(i=0;i<=curLength-pat.curLength;i++)//curlength是目标串的长度，pat.Length是模式串的长度{for(j=0;j<=pat.curlength;j++)//从ch[i] 开始的子串与模式串pat.ch进行比较if(ch[i+j]!=pat.ch[j])break;//ch是存放字符串的指针if(j==pat.curlength)return i;}return -1//找不到返回-1} 2. KMP算法(最大特点是不回溯)int fastFind(int next[]){int posP=0;posT=0;//两个串的扫描指针int lengthP=pat.curLength;int lengthT=curLength;while(posP<lengthP&&posT<lengthT)if(posP==-1||pat.ch[posP]==ch[posT]){posP++;posT++;}else posP=next[posP];if(posP<lengthP)return -1;//失败else return posT-lengthP;} //计算next[j]的算法void getNext(int next[]){int j=0,k=-1,lengthP=curLength;next[0]=-1;while(j<lengthP)if(k==-1||ch[j]==ch[k]){j++;k++;</p><p>next[j]=k;</p><p>}else k=next[k];}只是思路，不能直接上机实现，如果你能理解next[j]的原理，就很简单了，希望对你有帮助。
㈢ 求 JAVA 字符串匹配 完美算法
只需要实例化 类Matching 设置参数 并调用m.getIndex()方法就OK 请测试... public class Test18{
public static void main(String[] args){
Matching m = new Matching();
m.setOrgStr("ALSKLSHFKDLLS");
m.setSubStr("LS");
System.out.println(m.getIndex());
}
}
class Matching{
String orgStr ="";
String subStr ="";
public void setOrgStr(String orgStr){
this.orgStr = orgStr;
}
public void setSubStr(String subStr){
this.subStr = subStr;
}
public String getIndex(){
StringBuffer sb = new StringBuffer("{");
//根据关键字subStr来拆分字符串orgStr所得的字符串数组
String[] sub = orgStr.split(subStr);
int keyLength = subStr.length(); //关键字长度
int keySize = 0; //关键字个数
int subSize = sub.length; //子字符串个数
int subLength = 0; //子字符串长度
if(!orgStr.endsWith(subStr)){
keySize = subSize-1;
}else
keySize = subSize; int[] index = new int[keySize];//关键字下标数组
for(int i=0;i<keySize;i++){
subLength = sub[i].length();
if(i==0){
index[i]=subLength;
}else
index[i]=index[i-1]+subLength+keyLength;
}
if(keySize>0){
int l = keySize-1;
for(int i=0;i<l;i++){
sb.append(index[i]+",");
}
sb.append(index[l]);//最后一个关键字下标
}else{
sb.append("NULL");
}
sb.append("}");
return sb.toString();
}
}
㈣ c语言字符串匹配
1、c语言字符串匹配可以用strcmp函数。
2、strcmp是比较两个字符串的大小,两个字符串相同时返回0,第一个字符串大于第二个字符串时返回一个正值,否则返回负值.
比较两个字符串的算法是:逐个比较两个串中对应的字符，字符大小按照ASCII码值确定，从左向右比较，如果遇到不同字符，所遇第一对不同字符的大小关系就确定了两个字符串的大小关系，如果未遇到不同字符而某个字符串首先结束，那么这个字符串是较小的，否则两个字符串相等。
㈤ 求字符串匹配BM算法的代码，要c或者c++的。
BM算法的C语言实现：
// 函数：int* MakeSkip(char *, int)
// 目的：根据坏字符规则做预处理，建立一张坏字符表
// 参数：
// ptrn => 模式串P
// PLen => 模式串P长度
// 返回：
// int* - 坏字符表
int* MakeSkip(char *ptrn, int pLen)
{
int i;
//为建立坏字符表，申请256个int的空间
//PS:之所以要申请256个，是因为一个字符是8位，
// 所以字符可能有2的8次方即256种不同情况
int *skip = (int*)malloc(256*sizeof(int));
if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}
//初始化坏字符表，256个单元全部初始化为pLen
for(i = 0; i < 256; i++)
{
*(skip+i) = pLen;
}
//给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋值了
while(pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--;
}
return skip;
}
// 函数：int* MakeShift(char *, int)
// 目的：根据好后缀规则做预处理，建立一张好后缀表
// 参数：
// ptrn => 模式串P
// PLen => 模式串P长度
// 返回：
// int* - 好后缀表
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
char c;
if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}
c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它
*sptr = 1;//以最后一个字符为边界时，确定移动1的距离
pptr--;//边界移动到倒数第二个字符（这句是我自己加上去的，因为我总觉得不加上去会有BUG，大家试试“abcdd”的情况，即末尾两位重复的情况）
while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;
//该do...while循环完成以当前pptr所指的字符为边界时，要移动的距离
do{
while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最后一个字符c匹配的字符所指向的位置
p2 = ptrn + pLen - 2;
p3 = p1;
while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环，判断在边界内字符匹配到了什么位置
}while(p3 >= ptrn && p2 >= pptr);
*sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中，以pptr所在字符为边界时，要移动的位置
// PS:在这里我要声明一句，*sptr = （shift + pLen - sptr） + p2 - p3;
// 大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的。
// 因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里*sptr保存的内容，实际是指标要移动
// 距离，而不是字符串移动的距离。我想SNORT是出于性能上的考虑，才这么做的。
pptr--;//边界继续向前移动
}
return shift;
}
// 函数：int* BMSearch(char *, int , char *, int, int *, int *)
// 目的：判断文本串T中是否包含模式串P
// 参数：
// buf => 文本串T
// blen => 文本串T长度
// ptrn => 模式串P
// PLen => 模式串P长度
// skip => 坏字符表
// shift => 好后缀表
// 返回：
// int - 1表示成功（文本串包含模式串），0表示失败（文本串不包含模式串）。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//计算字符串是否匹配到了尽头
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
return 1;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}
㈥ 字符串匹配算法是怎么算的
这是一个毕业老师出的字符串的算法的题目！这是答案 可以参考一下！ 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); } }
㈦ Java编程实现字符串的模式匹配
传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。
KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。
㈧ 如何用c++实现对txt文件的简单字符串匹配算法
char *subString(char *str,int star,int len) 这个原型声明没有问题，传递进去一个字符串，起始字符的位置，以及截取的长度。按照这个意思来写最后是没有问题的。返回值为字符型指针 可以在这个函数里面声明一个字符数组，最后将这个字符数组返回。
㈨ 字符串的模式匹配算法
#include<iostream>
using namespace std;
void Next(char T[],int next[])
{ next[0]=-1;
int j=0,k=-1;
while(T[j]!='\0')
if((k==-1)||(T[j]==T[k]))
{ j++;
k++;
next[j]=k;
}
else k=next[k];
}
int KMP(char S[],char T[])
{ int i=0,j=0;
int next[10];
Next(T,next);
while((S[i]!='\0')&&(T[j]!='\0'))
{ if(S[i]==T[j]) {i++;j++;}
else j=next[j];
if(j==-1)
{ i++;j++; }
}
if(T[j]=='\0') return(i-j+1);
else return 0;
}
int main()
{ char a[100],b[100];
cout<<"please enter primary string :";
cin.getline(a,100);
cout<<"please enter substring:";
cin.getline(b,100);
if(KMP(a,b)==0)
cout<<"not exist!\n";
else cout<<"location is:"<<KMP(a,b)<<endl;
return 0;
}
具体的你自己看吧。
㈩ 字符串查找匹配--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）字符：