主题：第52次编程比赛新题目
crossbow [专家分：150] 发布于 2007-04-22 18:06:00
（因为晚上突然有安排，所以只能提早一点了）
（同麻烦bm设置sticky）
给出一个由小写字母组成的串s和一个不超过s的长度的正整数l，求s所有长度不小于l的字串中在s中不重叠地重复出现次数最多的子串。只要输出这个子串出现的次数就行了。
特别强调：子串不是子序列，必须是从s截出来连续的一段。s也是自身的子串。
例如
s = "abcabc", l = 3，
那么输出2，因为所求的子串是abc。
再例如
s = "ababa", l = 3，
那么输出1，长度不小于3的字串包括aba, bab, abab, baba, ababa。其中后面四个显然都只出现一次。前一个aba和后一个aba重叠了一个a，所以只能算不重叠地出现了一次。
实现接口
int solve(const char *s, int l);
s和l意思如上。通过返回值返回答案。
最后更新于：2007-04-22 18:51:00
回复列表 （共38个回复）
21 楼
fOrmkNight [专家分：0] 发布于 2007-04-24 22:12:00
数据范围有多大啊？
22 楼
烈焰燃烧 [专家分：2400] 发布于 2007-04-25 03:10:00
#include <cstring>
#include <iostream>
using namespace std;
int count(const char *s,char *t,int start)
{
int i,j;
int flag = 1;
i = start;
j = 0;
if( s==NULL || t==NULL )
return 0;
while( *(s+i)!='\0' )
{
while(*(t+j)!='\0')
{
if( *(t+j) != *(s+i) )
break;
else
{
i++;
j++;
}
}
if( strlen(t) == j )
{
flag++;
j = 0;
}
else
{
j = 0;
i = i-j+1;
}
}
return flag;
}
char* make(const char *s,int start,int l)
{
char *p;
int n = strlen(s);
p = (char *)malloc((l+1)*sizeof(char));
int j,i;
for( j = 0,i = start;j < l;j++,i++ )
{
*(p+j) = *(s+i);
}
*(p+j) = '\0';
return p;
}
int solve(const char *s, int l)
{
char *p;
int n = strlen(s);
int max=1,flag;
for(int i = 0;i < n;i++ )
{
for(int k = l; k < n; k++)
{
if( (k+i) < n )
{
p = make(s,i,k+i);
flag = count(s,p,0);
if(flag > max)
max = flag;
free(p);
}
}
}
return max;
}
23 楼
zhaoyg [专家分：4790] 发布于 2007-04-25 08:16:00
这一次在原来的基础上做了一点改进
int solve(const char *s, int l)
{
int max=1;//表示最大次数
int i,j,k,lenth,take,ls,p;
//ls为原始字符串的长度
int a[10000];
//读取样本字符串的数组
int count1=0,t=0;
//t记录样本字符串在原字符串中出现的次数
for (ls=0;s[ls];ls++) //计算原字符串长度
;
for (i=0;i<=ls-l;i++) //此处i用来控制启示位置,ls-l表示样本字符串活动范围
{
for (lenth=l;lenth<=ls-i;lenth++) //lenth表示样本字符串的长度
{
for (take=i,p=0;take<lenth+i;take++,p++) //读取起始位置为i长度为lenth的字符串
{
a[p]=s[take];
}
for (j=0;j<=ls-lenth;) //在原字符串中开始寻找一样的字符串
{
for (k=j,p=0;k<lenth+j;k++,p++)
{
if (a[p]==s[k])
{
count1++; //统计在同样长度下相同字符的个数
}
else
{
count1=0;
break;
}
}
if (count1==lenth) //成立则表明有相同的字符串
{
t++; //t为次数
if (t>max) max=t;
j=j+lenth;// 避免出现重叠例如"ababa" 只能算出现一次"aba"
count1=0;
}
else j++;
}
t=0;//归零
}
}
printf("最大次数为%d\n",max);
return max;//返回最大的次数
}
24 楼
hby222xl [专家分：0] 发布于 2007-04-25 09:25:00
3q
25 楼
zheni [专家分：60] 发布于 2007-04-25 10:38:00
int slove(const char *s,int l)
{
int n=0,i,j,c,k,p;
int max=1,m;
int *next;
char *d;
while(s[n]!='\0'){n++;};
d=(char *)malloc((n+1)*sizeof(char));
next=(int *)malloc((n+1)*sizeof(int));
for(;l<n/2+1;l++){
d[l+1]='\0';
for(p=0;p<n-2*l+1;p++){
m=0;
for(k=0;k<l;k++)
d[k+1]=s[p+k];
i=1;j=0;next[1]=0;
while(i<l){
if(j==0||d[i]==d[j]){
i++;j++;
if(d[i]!=d[j])
next[i]=j;
else
next[i]=next[j];
}
else j=d[j];
}
i=p+l;
do{
j=1;
m++;
while(i<n&&j<=l){
if(j==0||d[j]==s[i]){
i++;
j++;
}
else
j=next[j];
}
}while(j>l);
if(m>max) max=m;
}
}
return max;
}
26 楼
zhang_3shi [专家分：0] 发布于 2007-04-25 12:10:00
貌似难度比较高啊
27 楼
david2211 [专家分：560] 发布于 2007-04-25 13:30:00
新手勉力一试 如有错误 希望楼主给予指导
#include<stdio.h>
#include<string.h>
#define N 100
int solve(const char *s, int l)
{
int len,k,i,j,m,n;
int num[50][50];
len=strlen(s);
if(l<=len)
{
for(i=l;i<=len;i++)
{
for(j=0;j<len;j++)
{
k=1;
n=j;
for(m=j+i;m<len;m++)
{
if(s[n]==s[m])
{
n++;
if((n-j)>=i)
{
n=j;
k++;
}
}
else
{
m=m+j-n;
n=j;
}
}
num[i][j]=k;
}
}
for(i=0;i<50;i++)
{
for(j=0;j<50;j++)
{
if(num[0][0]<num[i][j])
num[0][0]=num[i][j];
}
}
return num[0][0];
}
}
void main()
{
char s[N];
int l,jg;
printf("请输入一串字符");
gets(s);
printf("请输入一个整数");
scanf("%d",&l);
jg=solve(s,l);
printf("%d",jg);
}
28 楼
hj36277 [专家分：130] 发布于 2007-04-25 17:32:00
int solve(char *s, int l)
{
int len,len1,i,m=1,k,p;
len1=len=strlen(s);
if(l>len)
exit(0);
if(l>len/2)
return 1;
for(p=0;p<=len-l;p++,len1--)
{
k=1;i=0;
while(l<=(strlen(s+p+l+i)))
{
if(!strncmp(s+p,s+p+l+i,l))
{
i+=l-1;
k++;
}
i++;
}
if(k>m)
m=k;
}
return m;
}
29 楼
小黑骑DK [专家分：610] 发布于 2007-04-25 18:19:00
/*
（因为l和1很象，所以我用m来代替了，没有问题吧 ?）
（还有个就是楼主没有说串的最大长度不超过多少，所以我偷下懒，直接用int类型来表示了）
*/
#include <stdio.h>
#include <string.h>//strlen
int solve(const char *s, int m);
int main(void)
{
const char *s = "ababababababababacba";
printf("%d\n", solve(s,2));
return 0;
}
int solve(const char *s, int m)
{
if (m <= 0)
{
return 0;
}
else
{
int length = strlen(s);
int start1 = 0, start2 = 0;//两个待比较子串的起点
int i = 0, times = 1, timesMax = 1;//比较时使用的记数器
for (start1=0; start1 <= (length+1 - (timesMax+1)*m); times = 1,start1++)
{
for (start2=(start1+m); start2 <= (length-m+1); start2++)
{
for (i=0; i<m && *(s+start1+i) == *(s+start2+i); i++)
;//判断两个子串是否相同
if (i == m)//相同
{
times++;
start2 += (m-1);
}
}
if (times > timesMax)
{
timesMax = times;
}
}
return timesMax;
}
}
30 楼
liyanguestc [专家分：90] 发布于 2007-04-25 19:55:00
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 1024*8 //s的最大长度
int next[N];
char s[N];
int le;
void get_next(int begin,int end)
{
int i,j;
next[begin]=begin-1;
i=begin;j=begin-1;
while(i<=end)
{
if(j==begin-1||s[i]==s[j])
{
i++;
j++;
if(s[i]!=s[j])
next[i]=j;
else next[i]=next[j];
}
else j=next[j];
}
}
int Index_KMP(int pos,int len1,int tbegin,int tend)
{
int i=pos;
int j=tbegin;
int len2=tend-tbegin+1;
while(i<len1&&j<=tend)
{
if(j==tbegin-1||s[i]==s[j])
{
i++;
j++;
}
else j=next[j];
}
if(j>tend)
return i-len2;
else
return -1;
}
int solve(const char *s,int le)
{
int flag[N],max;
max=0;
memset(flag,0,sizeof(flag));
int i,len,pos;
len=strlen(s);
for(i=0;i<=len-le;i++)
{
get_next(i,i+le-1);
if(flag[i]!=-1)
flag[i]=1;
else continue;
pos=i;
while(pos!=-1)
{
pos=Index_KMP(pos+le,len,i,i+le-1);
if(pos!=-1)
{
flag[pos]=-1;
flag[i]++;
}
}
if(flag[i]>max)max=flag[i];
}
printf("%d\n",max);
return 0;
}
int main()
{
scanf("%s%d",s,&le);
solve(s,le);
return 0;
}
我来回复
您所在位置：