字符串搜索算法

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

字符串搜索算法(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,所以另有更快速的算法。

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

相关

  • 语义网络语义网络(英语:Semantic Network)常常用作知识表示的一种形式。它其实是一种有向图;其中,顶点代表的是概念,而边则表示的是这些概念之间的语义关系。语义网络是机读型字典(machine-
  • 环甲韧带环甲韧带(cricothyroid ligament;conus elasticus)由两个部分组成:在紧急情况之环甲膜切开术(英语:Cricothyrotomy)则切断韧带。这种韧带的主要目的是保持环状软骨和甲状软骨不要分
  • 反刍动物反刍亚目(学名:Ruminantia)是偶蹄目中的一个亚目,其中的动物均是食草性动物,拥有分为多个胃室的胃进行反刍的动作。通过这个结构反刍亚目的动物,可以通过微生物消化其他只有一个胃
  • 乔治四世乔治四世(英语:George IV,1762年8月12日-1830年6月26日),全名乔治·奥古斯塔斯·腓特烈(英语:George Augustus Frederick),英国王室成员,1762年至1820年以王储身份出任威尔士亲王,1811年
  • 沙克尔顿坑沙克尔顿陨石坑(Shackleton)是位于月球南极的一座撞击坑,其地质龄大约有36亿年,在南极至少已存在了20亿年。其名称取自盎格鲁爱尔兰人南极探险家欧内斯特·亨利·沙克尔顿爵士(1
  • 受虐癖受虐癖(英语:masochism)是一种喜欢被虐待的嗜好。遭受他人的欺负、虐待,以此得到满足感。让自己被虐,如遭受鞭打、捆绑、羞辱等,来获得性兴奋或快感,可属一种性欲倒错。受虐癖的英
  • 巴德利工作记忆模型巴德利工作记忆模型(英文:Baddley's model of working memory)是艾伦·巴德利(Alan Baddeley)(英语:Alan Baddeley)和格雷厄姆·希奇(Graham Hitch)(英语:Graham_Hitch)在1974年提出
  • 扇形扇形(Circular sector)指圆上被两条半径和半径所截之一段弧所围成的图形。因形状如一把扇子而得名。扇形的弧长∝圆心角。扇形的面积∝圆心角:扇形的面积∝弧长:扇形面积的积分
  • 19651965年欧洲歌唱大赛(Gran Premio Eurovisione della Canzone 1965)为欧洲歌唱大赛之第十届比赛,于1965年3月20日在意大利那不勒斯举行,由卢森堡获胜,这是该国在大赛中第二次获胜
  • 梅萨县梅萨县(英语:Mesa County, Colorado)是美国科罗拉多州西部的一个县,西与犹他州相连。面积8,653平方公里。根据美国2000年人口普查,共有人口116,255人。县治大章克申(Grand Junctio