主题：第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个回复）
11 楼
35434464 [专家分：0] 发布于 2007-04-23 23:31:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
12 楼
35434464 [专家分：0] 发布于 2007-04-23 23:31:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
13 楼
35434464 [专家分：0] 发布于 2007-04-23 23:31:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
14 楼
35434464 [专家分：0] 发布于 2007-04-23 23:31:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
15 楼
35434464 [专家分：0] 发布于 2007-04-23 23:31:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
16 楼
35434464 [专家分：0] 发布于 2007-04-23 23:32:00
你好，有个小问题想请教你，请帮帮忙，明天要交作业,我实在是做不出来了。
有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，4....n，坐在编号为1，2，3，4...从1开始报数，数到m的人出列；下一个又从1开始报数，数到第2个m出列。是一个约瑟夫问题。要求用循环链表输出！
我的问题是数数时怎么保证数据从1开始。以为链表结点都是从0开始的？
还有定义i=1,开始，链表输出了乱码！正确的应该怎么做？？
请帮帮我，先谢谢了35434464@163.com
17 楼
crossbow [专家分：150] 发布于 2007-04-24 13:03:00
// 占个位置放reference solution
// Part 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <limits.h>
#define max(a, b) ((a) >= (b) ? (a) : (b))
void suffix_array(const char *s, int *SA, int *rank, int L)
{
int *c = (int*)malloc(sizeof(int) * max(L, CHAR_MAX + 1));
int *sa = (int*)malloc(sizeof(int) * max(L, CHAR_MAX + 1));
int *rk = (int*)malloc(sizeof(int) * max(L, CHAR_MAX + 1));
int i, j, r, c0, c1, h;
for (i = 0; i <= CHAR_MAX; i++)
c[i] = 0;
for (i = 0; i < L; i++)
c[(int) s[i]]++;
for (i = 1; i <= CHAR_MAX; i++)
c[i] += c[i - 1];
for (i = L - 1; i >= 0; i--)
SA[--c[(int) s[i]]] = i;
r = 0;
c0 = -1;
for (i = 0; i < L; i++)
{
if (s[SA[i]] != c0)
{
r++;
c0 = s[SA[i]];
}
rank[SA[i]] = r;
}
for (h = 1; h < L && r < L; h *= 2)
{
for (i = 0; i < h; ++i)
sa[i] = L - h + i;
for (j = 0; j < L; ++j)
if (SA[j] >= h)
sa[i++] = SA[j] - h;
for (i = 0; i <= r; i++)
c[i] = 0;
for (i = 0; i < L; i++)
c[rank[i]]++;
for (i = 1; i <= r; i++)
c[i] += c[i - 1];
for (i = L - 1; i >= 0; i--)
SA[--c[rank[sa[i]]]] = sa[i];
memcpy(rk, rank, sizeof(int) * L);
r = 0;
c0 = -1;
c1 = -1;
for (i = 0; i < L; i++)
{
int t = SA[i] + h < L ? rk[SA[i] + h] : 0;
if (rk[SA[i]] != c0 || t != c1)
{
r++;
c0 = rk[SA[i]];
c1 = t;
}
rank[SA[i]] = r;
}
}
for (i = 0; i < L; i++)
rank[i]--;
free(c);
free(sa);
free(rk);
}
void compute_lcp(const char *s, const int *SA, const int *rank, int *lcp, int L)
{
int i, j;
lcp[0] = 0;
for (i = 0; i < L; i++)
{
if (rank[i] > 0)
{
j = (i > 0 ? max(lcp[rank[i - 1]] - 1, 0) : 0);
while (s[i + j] == s[SA[rank[i] - 1] + j])
j++;
lcp[rank[i]] = j;
}
}
}
18 楼
crossbow [专家分：150] 发布于 2007-04-24 13:03:00
// Part 2
int core_algo(int l, const int *SA, const int *lcp, int L)
{
int i, j, k;
for (i = 1; i < L && lcp[i] < l; i++)
;
if (i < L)
{
int best = 1;
int **list = (int**)malloc(sizeof(int*) * L);
int *len = (int*)malloc(sizeof(int) * L);
int *index = (int*)malloc(sizeof(int) * L);
int *seq = (int*)malloc(sizeof(int) * L);
int count = 0;
memset(seq, -1, sizeof(int) * L);
i = 1;
while (i < L)
if (lcp[i] >= l)
{
for (j = i + 1; j < L && lcp[j] >= l; j++)
;
len[count] = j - i + 1;
list[count] = (int*)malloc(sizeof(int) * len[count]);
for (i--; i < j; i++)
seq[SA[i]] = count;
count++;
}
else
i++;
memset(index, 0, sizeof(int) * count);
for (i = 0; i < L; i++)
if ((k = seq[i]) != -1)
list[k][index[k]++] = i;
for (k = 0; k < count; k++)
{
if (len[k] > best)
{
int last = -l;
for (i = 0, j = 0; i < len[k]; i++)
if (list[k][i] - last >= l)
{
last = list[k][i];
j++;
}
best = max(best, j);
}
free(list[k]);
}
free(list);
free(len);
free(index);
free(seq);
return best;
}
else
return 1;
}
int solve(const char *s, int l)
{
int L = strlen(s);
int *SA = (int*) malloc(sizeof(int) * L);
int *rank = (int*) malloc(sizeof(int) * L);
int *lcp = (int*) malloc(sizeof(int) * L);
int r;
suffix_array(s, SA, rank, L);
compute_lcp(s, SA, rank, lcp, L);
r = core_algo(l, SA, lcp, L);
free(SA);
free(rank);
free(lcp);
return r;
}
#define MAXL 1000000
int main(void)
{
char *s = (char*) malloc(sizeof(char) * (MAXL + 1));
int l;
scanf("%s %d", s, &l);
printf("%d\n", solve(s, l));
free(s);
return 0;
}
19 楼
zhaoyg [专家分：4790] 发布于 2007-04-24 18:23:00
尽管谈不上什么高效，但毕竟对于初学者的我来说能够坐下来就已经很不错了
ps：由于我是第一次参与比赛，对于结果的处理我不知道是返回数值还是直接打印出来，于是我两个都用了，还望版主见谅。
int solve(const char *s, int l)
{
int i,j,k,t=0,lenth,take,ls,p,t1=0;
//ls为原始字符串的长度
int a[100000];
//读取样本字符串的数组
int count1=0,count[100000]={0};
//count数组记录样本字符串在原字符串中出现的次数,当其为0是表示只有一个
int temp;
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];
}
t1++; //为数组count序号
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为次数
count[t1]=t;
j=j+lenth;// 避免出现重叠例如"ababa" 只能算出现一次"aba"
count1=0;
}
else j++;
}
t=0;//使次数归零
}
}
for (i=0;i<t1;i++)//从大到小排序
{
for (j=0;j<t1;j++)
{
if (count[j]<count[j+1])
{
temp=count[j];
count[j]=count[j+1];
count[j+1]=temp;
}
}
}
printf("最大次数为%d\n",count[0]);
return count[0]; //返回最大的次数
}
20 楼
latalata [专家分：60] 发布于 2007-04-24 21:41:00
修改一下,加上修饰符const:
int solve(const char *s, int l)
{
int MAX,TEMP_MAX,Length,i,j,k;
MAX = 0;
Length=0;
const 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;
}
我来回复
您所在位置：