2009腾讯创新大赛 题四

[higer]

String
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 1063 Accepted: 63

Description

给定一个字符串S[1..n]和一个整数T，现在需要在字符串S中找出长度不小于T的一个子串，使得其在原串中不重叠出现的次数最多，求这个次数。
Input

第一行：一个整数T(T > 1)
第二行：一个字符串S，且仅包含小写字母，字符串长度不超过10000

Output

一个整数。代表出现最多的次数
如果没有满足条件的解则输出0
Sample Input

2
ababab
Sample Output

3

[王海龙]

算法思想:
1,如果一个串出现的次数为n,则其子串出现的次数必然不小于n.故该题本质上是求长度为T的各种子串的最大出现次数.
2,于是,将问题转化为类似于下面的问题:求一组数中出现的相同元素的最大次数.
例: 1, 2, 2, 3, 1, 4, 1 这组数中出现次数最多的是元素1,所以最大次数是3.

程序如下:

int myStrCom(const char * str, const char * dst, int len)
{ // 用于比较长度为len的两个串
int i = 0;
while (i < len)
{
if (*(str + i) == *(dst + i))
{
;
}
else
{
return (*(str + i) - *(dst + i));
}

i++;
}

return 0;
}

void maxNumString()
{
int T;
char str[10000 + 1] = "";

cin >> T;
cin >> str;

int len = strlen(str);
if (len < T)
{
cout << 0;
return ;
}
else if (len == T)
{
cout << 1;
return ;
}

bool flag[10000 + 1] = {false};
int curLen = len - T + 1;
int max = 0;
for (int i = 0; i <= len - T; i++)
{
if (flag[i] == true) // 已置相等标志，已经计算过了
{
continue;
}

int sum = 0;
for (int j = i + 1; j <= len - T; j++)
{
if (flag[j] == false) // 还未置相等标志，则需要比较
{
if (myStrCom(str + i, str + j, T) == 0)
{
sum++;
flag[i] = true; // 置相等标志
}
}
}

sum++; // 加上自身

if (sum > max)
{
max = sum;
}
}

cout << max;

[Ziyu Yu]

你这样做accepted了？
王海龙 写道:
> 算法思想:
> 1,如果一个串出现的次数为n,则其子串出现的次数必然不小于n.故该题本质上是求长度为T的各种子串的最大出现次数.
> 2,于是,将问题转化为类似于下面的问题:求一组数中出现的相同元素的最大次数.

[王海龙]

没法测了,是后来做的.
不知道呀.

[Ziyu Yu]

我也是这样暴力做的，没过。据说是官方测试数据错了。。。
王海龙 写道:
> 没法测了,是后来做的.
> 不知道呀.

[王海龙]

你主要看下我的思路啦.暴力太费时了.

----- Original Message -----
From: "Ziyu Yu" <yuziy...@gmail.com>
To: <bianchengai...@googlegroups.com>
Sent: Sunday, May 10, 2009 9:22 PM
Subject: Re: 2009腾讯创新大赛 题四

[Ziyu Yu]

你这也是暴力啊。我跟你做的一模一样。。。
n<10000,O(n^2)可以搞定啊。flag这个数组没有改变复杂度。。。
王海龙 写道:
> 你主要看下我的思路啦.暴力太费时了.
>

[王海龙]

时间复杂度的数量级是没有改变,都是O(n^2),但实际执行时要快很多.

相对于暴力破解,主要优化在于:

1 如果该串已经统计过了,就不再统计了.
比如: 1 2 3 1 1 3 1, 对于第4,5,7这三个校置上的1都不需要再计算了,暴力破解则需要.

2 通过bool比较使串的比较不再必要,这使得系统从比较次数从T转为1.

----- Original Message -----
From: "Ziyu Yu" <yuziy...@gmail.com>
To: <bianchengai...@googlegroups.com>
Sent: Sunday, May 10, 2009 9:33 PM
Subject: Re: 2009腾讯创新大赛 题四