字符串搜索算法

✍ dations ◷ 2025-12-10 12:09:59 #字符串匹配算法

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

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

相关

形式逻辑逻辑（古希腊语：λογική；德语：Logik；法语：logique；英语：logic；意大利语、西班牙语、葡萄牙语: logica），又称理则、论理、推理、推论，是对有效推论的哲学研究。逻辑被使用在大部分的
内含子内含子（英语：Intron）是一个基因中非编码DNA片段，它分开相邻的外显子。更精确的定义是：内含子是阻断基因线性表达的序列。DNA上的内含子会被转录到前体RNA中，但RNA上的内含子会在RN
国安局中华民国国家安全局（简称国安局）是中华民国国家安全会议唯一的附属机关，也是中华民国最主要的情报机构，主要进行统合国家情报、策划特种勤务两大工作，局本部位于阳明山磐石营区。
肃清大屠杀肃清大屠杀（又称大检证）是日军在第二次世界大战中占领新加坡和马来西亚时一个针对当地华人与反日分子有系统的种族清洗。虽然在1946年已经有人用“肃清”来形容这个大屠杀，新加
钟惠澜钟惠澜（1901年6月24日－1987年2月6日），广东梅县人，中国热带病学家，曾任北京大学人民医院院长。
Mollusca见内文软体动物门（学名：Mollusca）属于无脊椎动物，就其物种多样性而言，是动物界的第二大门，仅次于节肢动物门，其已确认的物种数量估计有十万多种。软体动物能适应许多不同环境，分布
罪恶宗教上的罪是指一种违反道德规范的行为或者实施了这种行为的状态。通常这种行为准则由一个神（如亚伯拉罕诸教中的天主；上帝、神；真主）来裁定。罪经常用于指称一种被禁止或不被认
四大家鱼淡水养殖的四大家鱼是指最为中国人所熟悉的四种食用鱼类。分别是青鱼、草鱼、鲢鱼、鳙鱼，它们都是属于辐鳍鱼纲鲤形目鲤科。经过一千多年的人工选择成为优良的淡水水产品种。
内-2内布拉斯加州第二国会选区（Nebraska's 2nd congressional district）是美国内布拉斯加州的一个众议员选区，选区范围为道格拉斯县（其中包含该州最大城市奥马哈）全部及萨皮县郊区。
口部 (部首)口部，是为汉字索引里为部首之一，康熙字典214个部首中的第三十个（三划的则为第一个）。就繁体字部首而言，字体主体可辨认为口，且无其他部首可用者将部首归为口部。要注意的是，口部与