字符串搜索算法

✍ dations ◷ 2025-11-23 00:40:07 #字符串匹配算法

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

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

相关

SPSSSPSS是统计产品与服务解决方案（Statistical Product and Service Solutions）的简称，为IBM公司的一系列用于统计学分析运算、数据挖掘、预测分析和决策支持任务的软件产品及相关
唐音陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文籀文 ‧ 鸟虫书 ‧ 篆书（大篆 ‧ 小篆）隶书 ‧ 楷书 ‧ 行书 ‧ 草书漆书 ‧ 书法 ‧ 飞白书笔画 ‧
pKa酸度系数（英语：Acid dissociation constant，又名酸解离常数，代号Ka、pKa、pKa值），在化学及生物化学中，是指一个特定的平衡常数，以代表一种酸解离氢离子的能力。该平衡状况是指由一种
准粒子准粒子（quasiparticles）或称集体激发（collective excitations）在物理学中，是一种发生在微观复杂系统的突现现象。例如固态系统中会好像存在着另一种虚拟的粒子。以电子在半导体
虫媒花虫媒花并不是一种花的名称，而是指某一类植物利用昆虫来传粉，让花进行受粉而传衍后代。这类植物也称虫媒授粉植物，是植物界里有花植物的授粉方式之一。传粉的方式除了自花受粉以
八大第一台八大第一台（又称：GTV第一台），是八大电视旗下的综合娱乐频道。2014年10月27日起，启用高清版本“八大第一台HD”。
汪敬煦汪敬煦（1918年5月30日－2011年9月17日），中华民国陆军二级上将，生于北京，籍贯浙江杭州，陆军官校14期工兵科、美国陆军工兵学校5期、美国陆军参谋大学正规班2期、三军大学战争学院59年
波兰陆军司令部波兰陆军是波兰武装力量下辖的一个兵种，现役人数77,000人。波兰陆军的一些部队随北约和欧盟在海外执行任务。自10世纪起，波兰就组建了自己的陆军。不过现代意义上的陆军到1918
道琼斯公司道琼斯公司为美国著名的出版财经信息出版品的公司。该公司于1882年由记者查尔斯·道，爱德华·琼斯，查尔斯·博格斯特莱斯创立。像纽约时报和华盛顿邮报一样，该公司虽然是公共交
时令河河流（江、河、江河、河道，古称水、川、河川，局地称溪、港、郭勒、沐沦、曲、藏布等）是自然汇入海洋、湖泊的流水，通常为淡水。在少数情况下，河流流入地下或者在汇入另一水体之前便