首页 > 代码库 > [NOI2014]
[NOI2014]
OJ题号：洛谷2375、BZOJ3670
思路：
一开始先写了一个裸的KMP，在求next数组（f数组）的时候加了一个判断j<<1是否>i+1（若大于则说明有重叠部分），后来发现并不能这样做。因为这样会影响到后面next数组的求值。后来看了一个题解，里面的思路是重新做一遍求next的过程，同时再判断是否超过一半。同时引入了num数组的概念，不过比较难理解，毕竟KMP整个才刚刚有点思绪。 参考:http://blog.csdn.net/zhaoyh2000/article/details/54866734
1 #define maxl 1000000+1 2 #define mod 1000000007 3 #include<string> 4 #include<iostream> 5 using namespace std; 6 int n,f[maxl],num[maxl]; 7 string s; 8 int main() { 9 ios::sync_with_stdio(false);10 cin>>n;11 while(n--) {12 cin>>s;13 f[0]=-1;14 f[1]=0;15 num[0]=0;16 num[1]=1;17 int j=0;18 unsigned long long ans=1ull;19 for(int i=1;i<(int)s.length();i++) {20 while(j>=0&&s[i]!=s[j]) j=f[j];21 f[i+1]=++j;22 num[i+1]=num[j]+1;23 }24 j=0;25 for(int i=1;i<(int)s.length();i++) {26 while(j>=0&&s[i]!=s[j]) j=f[j];27 j++;28 while((j<<1)>(i+1)) j=f[j];29 ans*=(unsigned long long)num[j]+1;30 ans%=mod;31 }32 cout<<ans<<endl;33 }34 return 0;35 }
[NOI2014]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。