首页 > 代码库 > HDU--1358--KMP算法失配函数getfail()的理解--Period
HDU--1358--KMP算法失配函数getfail()的理解--Period
/* Name: hdu--1358--Period Author: 日天大帝 Date: 20/04/17 10:24 Description: 长度/向后移动的位数 = 出现的次数 kmp其实匹配到了第str.size()位,这一位原本是‘\0‘的, 但是由于里面的递推下一位的关系,这一位其实也是匹配了的; */ #include<iostream> #include<cstring> using namespace std; void getfail(string); int f[1000009]; int main(){ int n,k = 0; ios::sync_with_stdio(false);//加上之后少了0.5s 700ms-200ms while(cin>>n,n){ string str;cin>>str; getfail(str); cout<<"Test case #"<<++k<<endl; for(int i=2; i<=str.size(); ++i){ // 注意i=str.size() if(f[i] > 0 && i%(i-f[i]) == 0){//(i-f[i])是KMP失配函数计算后失配时,向后移动的位数 cout<<i<<" "<<i/(i-f[i])<<endl; } } cout<<endl; } return 0; } void getfail(string s) { memset(f,0,sizeof(f)); //根据其前一个字母得到 for(int i=1;i<s.size();i++) { int j=f[i]; while(j && s[i]!=s[j]) j=f[j]; f[i+1]=(s[i]==s[j])?j+1:0; } }
HDU--1358--KMP算法失配函数getfail()的理解--Period
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。