锐客网

  1. 首页 > 睿知 > it技术 > >

kmp函数python python km算法

算法IT技术

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 thinkstrstrshould be slower than all the others? Do you know what algorithmstrstruses? I think it's quite likely thatstrstruses a fine-tuned, processor-specific, assembly-coded algorithm of theKMPtype or better. In which case you don't stand a chance of out-performing it inCfor such small benchmarks.
KMP 算法并非是所有线性复杂度算法中最快的 。在不同的环境（软硬件、测试数据等）下，KMP 与其变种乃至其他线性复杂度算法 ， 孰优孰劣都无法判断 。编译器在设计时考虑到诸多可能的因素，尽可能使不同环境下都能有相对较优的策略来得到结果 。因而，在保证结果正确的情况下 ， 与其根据算法原理自行编写，不如直接使用标准库中提供的函数 。
同时本次实测也在运行时间角度再次印证 Python 并不适合在算法竞赛中取得高成绩的说法，你们觉得呢？平仑区留下你的看法 。
急~求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;
【kmp函数python python km算法】}
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;
}
python 报错报错
第二段的意思是说：提示这意味着已将OpenMP运行时的多个副本链接到程序中 。这很危险，因为它会降低性能或导致错误的结果 。最好的办法是确保仅将单个OpenMP运行时链接到该流程中，例如 通过避免在任何库中静态链接OpenMP运行时 。作为不安全，不受支持，未记录的解决方法，您可以设置环境变量KMP_DUPLICATE_LIB_OK = TRUE以允许程序继续执行，但可能导致崩溃或无提示地产生错误的结果 。
它提示设置环境变量，因此可以加入一下语句，然后即可成功运行：
关于kmp函数python和python km算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：在真机上运行flutter，flutter 真机

    下一篇：如何为50台电脑服务器进行配置？ 50台电脑服务器怎么配置