主题：第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个回复）
沙发
bruceteen [专家分：42660] 发布于 2007-04-22 21:42:00
我总觉得
求s所有长度不小于l的字串中在s中不重叠地重复出现次数最多的子串
等同于
求s所有长度 等于l的字串中在s中不重叠地重复出现次数最多的子串
板凳
csea [专家分：340] 发布于 2007-04-22 22:33:00
#include <iostream>
using namespace std;
//compare the strings in the range [p0,q0) and [p1,q1)
bool cmp(const char*s,int p0,int q0,int p1,int q1)
{
while (p0 < q0 && p1 < q1 && s[p0]==s[p1])
{
p0++;
p1++;
}
if (p0 < q0)return false;
else return true;
}
int solve(const char *s, int l)
{
int len = strlen(s),d,j,i,max,cnt;
max = 0;
for (d = l; d <= len; d++)
{
for (i = 0; i+d-1 < len; i++)
{
j = i+d;
if (j >= len)break;
cnt = 1;
for (; j+d-1 < len;)
{
if (cmp(s,i,i+d,j,j+d))
{
cnt++;
j = j+d;
}
else
{
j++;
}
}
if (cnt > max)max = cnt;
}
}
return max;
}
int main()
{
int l;
char s[100];
cin >> s >> l;
cout << solve(s,l) << endl;
system("pause");
return 0;
}
初次参赛，请多多指教^_^
编译环境Dev-C++
3 楼
luoyanxia [专家分：10] 发布于 2007-04-23 10:13:00
#include<stdio.h>
int solve(const char *s, int num)
{
int count=1,count1=0,i=0,j=0,k=0,m=0;
char sub[10],*str,*p;
str=p=s;
while(str[k]!='\0'){
m=0;
while(m<num){
sub[m]=str[k+m];
m++;
}sub[m]='\0';
p=s;
while(p[i]!='\0'){
j=0;
if(p[i]==sub[j]){
while(p[i]==sub[j]&&p[i]!='\0'){
i++;j++;
}
if(sub[j]=='\0')
count1++;
else
i=i-j+1;
}
else
i++;
}
count=count>count1?count:count1;
k++;
}
return count;
}
int main()
{
char *str;
int b,a;
str=(char *)malloc(100);
printf("print string\n");
scanf("%s",str);
printf("printf number\n");
scanf("%d",&a);
if(strlen(str)<a){
printf("error");
return 0;
}
b=solve(str,a);
printf("max num\n");
printf("%d",b);
getch();
return 0;
}
4 楼
toudu [专家分：130] 发布于 2007-04-23 13:23:00
好啊
5 楼
toudu [专家分：130] 发布于 2007-04-23 13:24:00
对了，我是新上论坛的，我想参加，怎么办啊
6 楼
maths_dxj [专家分：90] 发布于 2007-04-23 16:01:00
只需要考虑长度为l的子串
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int Solve(const char *s,int l)
{
int S_Length=0;
while (*(s+S_Length)!='\0')S_Length++;//to get length of the string
if (S_Length<l)
{
printf("Erro:l<strlen");
return 0;
} //Err inform
bool *flag=new bool[S_Length];
for (int m=0; m<S_Length;*(flag+m)=0,m++);
int Ubound1=S_Length-2*l;
int Ubound2=S_Length-l;
int Max=1; //Max number to get
int cnt=1;
// const char *substring;
// substring=s;//to store the sub sequence which appears with the max number in the string
for (int i=0; i<=Ubound1; i++)
{
if (*(flag+i)) continue;
for (int j=i+l; j<=Ubound2; j++)
{
if (*(flag+j)) continue;
for (int k=0; k<l&&(*(s+i+k) == *(s+j+k)) ;k++);
if(!(k-l))
{
cnt++;
*(flag+j)=1;
j=j+l-1;
}
}
if(Max<cnt)
{
Max=cnt;
// substring=s+i;
}
cnt=1;
}
delete[] flag;
// printf("the subString is:");
// for (int y=0;y<l;y++)
// printf("%c",*(substring+y));//print the substring
printf("\nMax String Number is:%d",Max);
return Max;
}
int main(void)
{
char String[1000];
for(int i=0;i<1000;i++)
*(String+i)='s';
*(String+1000)='\0';
int l;
printf("input l:");
scanf("%d",&l);
Solve(String,l);
system("pause");
return 0;
}
7 楼
ccpplus [专家分：0] 发布于 2007-04-23 19:12:00
/*
Name: ccpplus
Copyright:
Author:
Date: 23-04-06 18:59
Description: compiled with dev-C++ 4.9.8.0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int solve(const char*, int);
int main()
{
int minlen;
char s[128];
scanf("%s%d", s, &minlen); /*程序不保证输入数据的有效性*/
if(minlen > strlen(s)) {
printf("%d is bigger than the length of \"%s\"\n", minlen, s);
} else {
printf("%d\n", solve(s, minlen));
}
system("PAUSE");
return 0;
}
int solve(const char *s, int minlen) {
int max = 0;
int len = strlen(s);
char *string = (char*)malloc((len+1)*sizeof(char));
if(string == 0) {
printf("ERROR: ask for memory failed\n");
exit(0);
}
for(int size = minlen; size <= len; size++) {
for(int i = 0; i <= len-size; i++) {
int count = 0;
int last = -1; /*初始时，无任何字符串重叠*/
strncpy(string, &s[i], size);
for(int i = 0; i < len; i++){
if(last < i){ /*判断字符串是否重叠*/
if(strncmp(string, &s[i], size) == 0) {
/*更新上一字符串的串尾位置*/
last = i + size-1;
count++;
}
}
}
if(max < count) max = count;
}
}
free(string);
return max;
}
8 楼
latalata [专家分：60] 发布于 2007-04-23 22:14:00
int solve(char *s, int l)
{
int MAX,TEMP_MAX,Length,i,j,k;
MAX = 0;
Length=0;
char *p ,*q,*r,*t;
p=s;
while(*p!=NULL)
{
p++;
Length++;
}
if(Length<l)return 0;
else if(Length==1)return 1;
else
{
for(i=0;i<Length-i;i++)
{
p=s;
for(j=0;j<i;j++)p++;
TEMP_MAX=1;
j=0;
q=p;
while(j<l){
q++;
j++;
}
k=i+l;
while(k<=Length-l)
{
t=q;
r=p;
int c;
for(c =0;c<l;c++)
{
if(*t == *r)
{
t++;
r++;
}
else break;
}
if(c==l){
TEMP_MAX++;
q=t;
k=k+l;
}
else {
q++;
k++;
}
}
if(TEMP_MAX>MAX)MAX=TEMP_MAX;
}
}
return MAX;
}
9 楼
35434464 [专家分：0] 发布于 2007-04-23 23:08:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了。35434464@163.com
10 楼
35434464 [专家分：0] 发布于 2007-04-23 23:30:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
我来回复
您所在位置：