正文
kmp函数python python km算法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Python 和 C++ 下字符串查找速度对比，你觉得Python适合算法竞赛吗
一位同学最近在备战一场算法竞赛，语言误选了 Python ，无奈只能着手对常见场景进行语言迁移。而字符串查找的场景在算法竞赛中时有出现。本文即对此场景在 Python 和竞赛常用语言 C++ 下的速度进行对比，并提供相关参数和运行结果供他人参考。
本次实测设置两个场景：场景 1 的源串字符分布使用伪随机数生成器生成，表示字符串查找的平均情况；场景 2 的源串可连续分割成 20,000 个长度为 50 的字符片段，其中第 15,001 个即为模式串，形如“ab…b”（1 个“a”，49 个 “b”），其余的字符片段形如“ab…c”（1 个“a”，48 个“b”，1 个“c”）。
本次实测中，Python 语言使用内置类型 str 的 .find() 成员函数，C++ 语言分别使用 string 类的 .find() 成员函数、 strstr 标准库函数和用户实现的 KMP 算法。
IPython 的 %timeit 魔法命令可以输出代码多次执行的平均时间和标准差，在此取平均时间。C++ 的代码对每个模式串固定运行 1,000 次后取平均时间。
以下时间若无特别说明，均以微秒为单位，保留到整数位。
* 原输出为“2.63 ms”。IPython 的 %timeit 输出的均值保留 3 位有效数字，由于此时间已超过 1 毫秒，微秒位被舍弃。此处仍以微秒作单位，数值记为“2630”。
本次实测时使用的设备硬件上劣于算法竞赛中的标准配置机器，实测结果中的“绝对数值”参考性较低。
根据上表中的结果，在给定环境和相关参数条件下，场景 1 中 Python 的运行时间大约为 C++ 中 string::find 的五分之一，与 std:strstr 接近；而在场景 2 中 Python 的运行时间明显增长，但 C++ 的前两种测试方法的运行时间与先前接近甚至更短。四次测试中，C++ 的用户实现的 KMP 算法运行时间均较长，长于同条件下 Python 的情况。
Python 中的内置类型 str 的快速查找（ .find() ）和计数（ .count() ）算法基于 Boyer-Moore 算法 和 Horspool 算法 的混合，其中后者是前者的简化，而前者与 Knuth-Morris-Pratt 算法 有关。
有关 C++ 的 string::find 比 std::strstr 运行时间长的相关情况，参见 Bug 66414 - string::find ten times slower than strstr 。
Why do you think strstr should be slower than all the others? Do you know what algorithm strstr uses? I think it's quite likely that strstr uses a fine-tuned, processor-specific, assembly-coded algorithm of the KMP type or better. In which case you don't stand a chance of out-performing it in C for such small benchmarks.
KMP 算法并非是所有线性复杂度算法中最快的。在不同的环境（软硬件、测试数据等）下，KMP 与其变种乃至其他线性复杂度算法，孰优孰劣都无法判断。编译器在设计时考虑到诸多可能的因素，尽可能使不同环境下都能有相对较优的策略来得到结果。因而，在保证结果正确的情况下，与其根据算法原理自行编写，不如直接使用标准库中提供的函数。
同时本次实测也在运行时间角度再次印证 Python 并不适合在算法竞赛中取得高成绩的说法，你们觉得呢？平仑区留下你的看法。
相关问答
Q1: 急~求KMP算法
我这个编译没问题的. 你试试。如果要匹配更长的串kmp函数python，请修改前面的宏定义kmp函数python，或改用malloc的方法。
补充一下kmp函数python，这个是VC遍过的，windows下跑。
#include stdio.h
#include string.h
#include stdlib.h
#define MAX_S 101 //主串的长度最大值为100
#define MAX_P 21 //模式串的长度最大值为20
char s[MAX_S],p[MAX_P]; //s为主串，p为模式串
int nextv[MAX_P]; //p的nextv数组
void init_nextv()
{ int i=0,j=-1;
int p_len; //模式串的长度
p_len=strlen(p);
nextv[0]=-1;
while(ip_len-1)
{ if(j==-1||p[i]==p[j])
{ ++i;
++j;
if(p[i]!=p[j])
nextv[i]=j;
else
nextv[i]=nextv[j];
}
else
j=nextv[j];
}
}
int kmp()
{
int i=0,j=0,s_len,p_len;
s_len=strlen(s);
p_len=strlen(p);
while(is_lenjp_len)
{ if(j==-1 || s[i]==p[j])
{ i++;
j++;
}
else
j=nextv[j];
}
if(j==p_len)
return i-p_len;
else
return -1;
}
int main()
{
int index=0;
printf("请输入主串:");
scanf("%s",s);
printf("请输入子串:");
scanf("%s",p);
init_nextv();
index=kmp();
if(index!=-1)
printf("匹配成功，匹配位置%d\n",index);
else
printf("匹配失败\n");
system("pause");
return 0;
}
Q2: python 报错
报错
第二段的意思是说：提示这意味着已将OpenMP运行时的多个副本链接到程序中。 这很危险，因为它会降低性能或导致错误的结果。 最好的办法是确保仅将单个OpenMP运行时链接到该流程中，例如 通过避免在任何库中静态链接OpenMP运行时。 作为不安全，不受支持，未记录的解决方法，您可以设置环境变量KMP_DUPLICATE_LIB_OK = TRUE以允许程序继续执行，但可能导致崩溃或无提示地产生错误的结果。
它提示设置环境变量，因此可以加入一下语句，然后即可成功运行：
关于kmp函数python和python km算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
