首页 > 代码库 > 51nod 1277 字符串中的最大值(KMP算法)
51nod 1277 字符串中的最大值(KMP算法)
分析:
KMP算法:参考http://www.cnblogs.com/c-cloud/p/3224788.html,是一个线性处理字符串匹配问题的算法
在这里利用到next数组,记t[i]为长度为i的前缀出现的次数,显然t[n]=1。next[i]即为子串[0,i]的后缀与前缀重复的最长长度,因此可以统计一下next[i]的取值的个数,然后较长的前缀出现一次代表较短的前缀也一次,递推一下即可,复杂度为O(n)。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=1e5+5; 6 typedef long long ll; 7 int n,next[maxn],t[maxn]; 8 char s[maxn]; 9 int main(){ 10 // freopen("e:\\in.txt","r",stdin); 11 cin>>s; 12 n=strlen(s); 13 memset(next,0,sizeof(next)); 14 memset(t,0,sizeof(t)); 15 int q,k; 16 for(q=1,k=0;q<n;q++){ 17 while(k>0&&s[q]!=s[k]){ 18 k=next[k-1]; 19 } 20 if(s[k]==s[q]) 21 k++; 22 next[q]=k; 23 } 24 for(int i=n;i>0;i--){ 25 t[i]++; 26 t[next[i-1]]+=t[i]; 27 } 28 ll ans=0; 29 for(int i=1;i<=n;i++){ 30 if((ll)t[i]*i>ans)ans=(ll)t[i]*i; 31 } 32 cout<<ans<<endl; 33 return 0; 34 }
51nod 1277 字符串中的最大值(KMP算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。