老字号餐厅将福寿螺当田螺卖 官方称已立案调查
时间:2024-09-11 09:24:02
发布网友 发布时间: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); } }