-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2018-07-17
来源 ：
阅读 1203
评论 0
摘要：本文主要向大家介绍了Python语言算法：如何解决回文索引问题，通过具体的内容向大家展示，希望对大家学习Python语言有所帮助。
本文主要向大家介绍了Python语言算法：如何解决回文索引问题，通过具体的内容向大家展示，希望对大家学习Python语言有所帮助。
给定一个单词word和一个字符串S，找到S中的所有起始索引——word的回文。
例如，假设word是“ab”，并且S是“abxaba”，则返回0,3和4。
蛮力破解
对于这个问题野蛮的解决方案是遍历S中每个单词大小的窗口并检查它们是否是回文，如下所示：
这将花费O(|W| * |S|)时间。有没有更快的方法呢？
试试哈希
解决这个问题可以使用的一种方法是Rabin-Karp算法。基本思想是我们可以对目标word做一个基于频率的散列，并检查s下的任何窗口是否散列为相同的值。也就是说，散列将是每个字符和其频率的char * prime_num ** char_freq之和。如果word和窗口的散列匹配，则我们可以对两个字符串手动加上== 。因为预计冲突很少，所以时间将是O(S)。但是，解决这个问题有一个更简单的方法：
计数差异
请注意，沿着窗口移动意味着当实际只有一小部分更新的时候，重新计算整个窗口的频率计数。这种见解引导我们采取以下策略：
制作目标单词的频率字典
当我们沿着字符串前进时，持续比较差异
当字典为空时，窗口和单词匹配
我们通过增加窗口中的新字符并删除旧的字符来区分我们的频率字典。
这应该在O(S)时间运行。
本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言Python频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
