问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
你好,欢迎来到懂视!登录注册
当前位置: 首页 - 正文

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

发布网友 发布时间:2022-05-01 11:39

我来回答

1个回答

热心网友 时间:2023-10-10 06:19

这是一个毕业老师出的字符串的算法的题目!这是答案 可以参考一下! 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 ) { // *,白废功夫比了!看看需要向右移动几个 // 字符吧(如果说从右到左是本算法的核心,则 // 判断向右移几个字符则是本算法的技巧)。 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 C*Dlg::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); } }
声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。
E-MAIL:11247931@qq.com
lim(tan^3(3x)/(X^2sin(2x))(x趋近于0) 用等价无穷小计算下列极限,谢谢了,急。。 请问一下数学极限linit sin2x/tan3x如何求解,要过程,谢了,加急... lim(sin2x+x^2)/tan3x的极限怎么算 , x趋近于0 手机电池修复方法(手机用久了电池不耐用?教你一键修复) 数字电视如何填写参数 湖南电视台本振频率、下行频率、符号率 孩子太过于听话,为何是父母教育的失败? 炖牛肉怎么好吃 制作炖牛肉的方法 日产轩逸刹车油漏到真空泵里 老公跟老婆闹矛盾晚上睡觉那双筷子放在被面是什么意思? 怎样匹配两个特定字符间的内容? 陪嫁筷子和酒盅什么意思? 夫妻两个一双红筷,一双黑筷什么意思? 为什么把夫妻比作一双筷子呢? LCD屏和OLED屏幕怎么区分? 诈骗金额2千元群发5万条骗人信息如何定罪 中文字符匹配怎么做 夫妻分筷说明什么? 短信群发会有什么法律责任 华为手机怎么开起淘宝网同步设置 夫妻就像一双筷子,谁说的 短信诈骗案发送信息一万多条会判多久,诈骗金额4万多块会判多久 为什么说夫妻就像一双筷子呢? 群发短信30万条未获利被抓犯什么罪 我朋友犯团伙电话诈骗金额一共13万,现在马上到起诉阶段,他这种还有好久*才判决啊?会判多久? 群发诈骗短信犯罪怎样定刑 梦见带自己的小男孩在菜园里种菜 梦见我和女儿在寺庙菜园里种菜 梦见在菜园子里种菜花苗 ...过日子要像一双筷子:一是 谁也离不开谁;二是什么酸甜苦辣都能一起... ...俩过日子要像一双筷子:一是谁也离不开谁;二是什么酸甜苦辣都能在一... EXCEL字符匹配问题 女生说我可能要用筷子了什么意思? C语言 字符串匹配 日本miyachi焊接机多少钱 请问“夫妻”是什么? 字符串的匹配(JAVA) 国外好的激光焊接机有哪些? 字符串匹配(正则表达式) lcd oled屏幕区别 LCD和OLED这两个屏幕怎么区分呢? 如何区分LCD和OLED这两个屏幕? 华为荣耀9图标颜色怎么改 荣耀9控制栏图标颜色怎么更改? 抖音游戏入驻什么意思 入驻一个平台有什么要求吗 华为荣耀9青春版出现很多应用小图标? 入驻企业是什么意思 车险费改后车损险包含哪些
  • 焦点

热门图文

猜你喜欢