字符串搜索算法

✍ dations ◷ 2025-11-16 22:04:04 #字符串匹配算法

字符串搜索算法(String searching algorithms)又称字符串比对算法(string matching algorithms)是一种搜索算法,是字符串算法中的一类,用以试图在一长字符串或文章中,找出其是否包含某一个或多个字符串,以及其位置。

最直观的解法是比对,如下例中,在字符串haystack中找出字符串needle

char* haystack;char* needle;int hlen, nlen, found;int i,j,k;found = 0;hlen = strlen(haystack);nlen = strlen(needle);for (i = 0; i < hlen; ++i) {    for (j = 0; j < nlen; ++j) {        if (haystack != needle) break;        if (j == nlen - 1) found = 1;    };};return found;

上例中,若字符串needle存在于字符串haystack中,则传回1,否则传回0。

但是此直观算法的复杂度为 O(mn),其中haystack的长度为n、needle的长度为m,所以另有更快速的算法。

令 为模式的长度, 为要搜索的字符串长度, 为字母表长度。

相关

  • .mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ruby.large{font-size:250%}.mw-parser-output ruby.larger{fon
  • 科学学科学学是一门主要以经验方法对科学进行整体研究的综合性学科。是自然科学和社会科学综合产生的新兴交叉学科。是关于科学的科学。科学学向人们回答的问题主要是:究竟什么是科
  • 固氮生物固氮生物(英语:Diazotroph)多为细菌及古菌,能将空气中的氮气固定为较有用的形式,例如︰氨。固氮生物是能不透过外在资源而固氮的有机体。举例来说,这样的有机体包含︰根瘤菌及属于放射
  • 杜甫杜甫(712年2月12日-770年),字子美,号少陵野老,一号杜陵野客、杜陵布衣,唐朝现实主义诗人,其著作以弘大的社会写实著称。杜甫家族出于京兆杜氏分支,唐朝时京兆杜氏多自称为杜陵人。曾
  • 1498年重要事件重要人物
  • ppt万亿分率,台湾称兆分率,简称ppt(源自英语Parts Per Trillion的简写),定义为万亿分之一,1ppt即是万亿分之一分之一。1 p p t =
  • 伊法特伊法特苏丹国是中世纪在非洲之角的一个穆斯林王朝。伊法特国由瓦拉什马王朝建立,国家的中心是在塞拉和谢瓦古城。王国统治了今天埃塞俄比亚的东部、吉布提和索马里北部的部分
  • 谅解备忘录谅解备忘录,或称作了解备忘录(英语:Memorandum of understanding,缩写:MOU),是双方或多方签订的一种备忘录,仅用以记载不同国家、政府或组织间签署双边(英语:Bilateralism)或多边意向(动
  • 曲靖市曲靖市,古称味县、南宁,是中华人民共和国云南省下辖的地级市,位于云南省东部。市境西临昆明市,北接昭通市与贵州省毕节市,东邻贵州省六盘水市、黔西南州,南界红河州、文山州与广西
  • 甲米府甲米府(泰语:จังหวัดกระบี่,皇家转写:Changwat Krabi,泰语发音:),是泰国南部一个行政区,西北接攀牙府,南邻董里府,在东北及正北面与素叻府有很长的共同界线 ,东邻那空是贪