速度一定要比普通遍历方法快,求大佬🧍♂️
1条回答 默认 最新
- Clarence Liu 2021-07-02 21:00关注
#include <iostream> #include <cstring> using namespace std; const int MAXN = 2e5 + 100; int Next[MAXN]; int ans = 0; void Priefix_Table(string pattern){ Next[0] = Next[1] = 0; int j; int len = pattern.length(); for(int i=1;i<len;i++){ j = Next[i]; while(j && pattern[i] != pattern[j]) j = Next[j]; if(pattern[i] == pattern[j]) Next[i+1] = j + 1; else Next[i+1] = 0; } } void KMP(string text, string pattern){ int len_text = text.length(); int len_pattern = pattern.length(); int j=0; for(int i=0;i<len_text;i++){ while(j && text[i] != pattern[j]) j = Next[j]; if(text[i] == pattern[j]) j++; if(j == len_pattern) ans++; } } int main(){ string s1, s2; cin >> s1 >> s2;//s1为父串,s2为子串 Priefix_Table(s2); KMP(s1, s2); cout << ans; return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 delphi webbrowser组件网页下拉菜单自动选择问题
- ¥15 wpf界面一直接收PLC给过来的信号,导致UI界面操作起来会卡顿
- ¥15 init i2c:2 freq:100000[MAIXPY]: find ov2640[MAIXPY]: find ov sensor是main文件哪里有问题吗
- ¥15 运动想象脑电信号数据集.vhdr
- ¥15 三因素重复测量数据R语句编写,不存在交互作用
- ¥15 微信会员卡等级和折扣规则
- ¥15 微信公众平台自制会员卡可以通过收款码收款码收款进行自动积分吗
- ¥15 随身WiFi网络灯亮但是没有网络,如何解决?
- ¥15 gdf格式的脑电数据如何处理matlab
- ¥20 重新写的代码替换了之后运行hbuliderx就这样了