首页 > 代码库 > 51Nod 1277 字符串中的最大值(KMP,裸题)
51Nod 1277 字符串中的最大值(KMP,裸题)
1277 字符串中的最大值
题目来源： Codility
基准时间限制：1 秒
空间限制：131072 KB 分值: 80
难度：5级算法题
一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。
给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。
例如：S = "abababa" 所有的前缀如下:
"a", 长度与出现次数的乘积 1 * 4 = 4,
"ab",长度与出现次数的乘积 2 * 3 = 6,
"aba", 长度与出现次数的乘积 3 * 3 = 9,
"abab", 长度与出现次数的乘积 4 * 2 = 8,
"ababa", 长度与出现次数的乘积 5 * 2 = 10,
"ababab", 长度与出现次数的乘积 6 * 1 = 6,
"abababa", 长度与出现次数的乘积 7 * 1 = 7.
其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的。
Input
输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。
Output
输出所有前缀中字符长度与出现次数的乘积的最大值。
Input示例
abababa
Output示例
10
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1277
分析：kmp裸题，之后会补上纯板子
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=100010; 5 char x[maxn]; 6 int kmpnext[maxn]; 7 int len; 8 int res[maxn];///出现次数 9 void pre_kmp(char x[],int m,int kmpnext[])10 {11 int i,j;12 j=kmpnext[0]=-1;13 i=0;14 while(i<=m)15 {16 if(j==-1||x[i]==x[j])17 {18 kmpnext[++i]=++j;19 }20 else21 {22 j=kmpnext[j];23 }24 }25 return;26 }27 int main()28 {29 cin>>x;30 len=(int)strlen(x);31 pre_kmp(x,len,kmpnext);32 for(int i=len;i>=1;i--)33 {34 res[i]++;35 res[kmpnext[i]]+=res[i];36 }37 ll ans=0;38 for(ll i=1;i<=len;i++)39 {40 ans=max(ans,res[i]*i);41 }42 cout<<ans<<endl;43 return 0;44 }
51Nod 1277 字符串中的最大值(KMP,裸题)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。