黑马程序员技术交流社区

标题: 字符串找最大字串的问题。 [打印本页]

作者: Dreamsky_qihang 时间: 2015-3-18 11:20
标题: 字符串找最大字串的问题。
基础测试第十题的找最大子串。题目要求是多个字符串，但我看前辈们都做的是两个字符串的比较。
这个题的要求到底是多个字符串的字串呢？还是两个的就符合要求了？
两个的已经做出来额。多个的花，没有思路啊。

作者: Dreamsky_qihang 时间: 2015-3-18 11:35
来人发表一下意见。。我也好有个参考。。

作者: Dreamsky_qihang 时间: 2015-3-18 19:53
:'(没人吗

作者: wenfeng340 时间: 2015-3-18 22:07
是多个确实不好做我看了下好像效率高点的算法都是很晦涩难道什么后缀数组后缀树自动机什么的

作者: wenfeng340 时间: 2015-3-18 22:15
有个最笨的方法就是先找出字符串里面最短的那个然后在求出其所有的子字符串和其余的去比较如果是其余的字符串的子串就把子串的长度复制为一个maxlen 然后再循环比较得到符合条件的子串然后就和求其长度和maxlen比较

作者: 郑江 时间: 2015-3-19 00:14
#import <Foundation/Foundation.h>

int main()
{
NSArray *array = @[@"1234", @"2345", @"3456"];

NSString *string = array[0];

// 找出最短字符串并赋值给string
for (int i = 0; i < arra.count; i++)
{
if (string.length > [array[i] length])
string = array[i];
}

for (int i = (int)string.length; i > 0; i--)
{
int count = 0;

for(int j = 0; j <= string.length - i; j++)
{
//由长到短遍历string的所有子串
NSString *str = [string substringWithRange: NSMakeRange(j, i)];

//遍历所有字符串
for(int n = 0; n < array.count; n++)
{
//若字符串中包含str 则count+1
NSRange range = [array[n] rangeOfString: str];

if(range.location != NSNotFound)
count++;
}

//当count == 字符串数量，即所有字符串都包含str
if(count == array.count)
{
NSLog(@"最长公共字串为%@", str);

break;
}
}

if(count == array.count)
break;

count = 0;
}
return 0;
}

作者: Dreamsky_qihang 时间: 2015-3-19 08:43

wenfeng340 发表于 2015-3-18 22:07
是多个确实不好做我看了下好像效率高点的算法都是很晦涩难道什么后缀数组后缀树自动机什么的 ...

后面说的这些都不会。这咋整。。

作者: Dreamsky_qihang 时间: 2015-3-19 08:46

wenfeng340 发表于 2015-3-18 22:15
有个最笨的方法就是先找出字符串里面最短的那个然后在求出其所有的子字符串和其余的去比较如果是其 ...

我一开始的想法也和这差不多。但这个实现起来不现实啊。如果子串的程度够长的话，效率会很低。而且循环也不好写啊。。

作者: Dreamsky_qihang 时间: 2015-3-19 09:01

郑江发表于 2015-3-19 00:14
#import

int main()

这个是多个字符串的吗？待我拷贝下来理解一下:lol

作者: tianlin 时间: 2015-3-19 09:59
没做过这个题

作者: wenfeng340 时间: 2015-3-19 10:16

Dreamsky_qihang 发表于 2015-3-19 08:46
我一开始的想法也和这差不多。但这个实现起来不现实啊。如果子串的程度够长的话，效率会很低。而且循环也 ...

效率确实很低

作者: 贾永强 时间: 2015-3-19 11:52
我基础测试也有这个题目，我只写了两个字符串求最大子串的程序，得分了

作者: a380vs747` 时间: 2015-3-19 11:57

郑江发表于 2015-3-19 00:14
#import

int main()

自测题貌似是需要用c语言来写吧...

作者: Dreamsky_qihang 时间: 2015-3-19 11:59

贾永强发表于 2015-3-19 11:52
我基础测试也有这个题目，我只写了两个字符串求最大子串的程序，得分了

恩恩。多谢，就是怕给扣了分啊。。自荐信已经很低了。不能在在这扣无谓的分数了

作者: 岳挺 时间: 2015-3-19 13:30
楼上那位是oc实现的，基测好像没有oc题哎- -

作者: Dreamsky_qihang 时间: 2015-3-22 12:08

岳挺发表于 2015-3-19 13:30
楼上那位是oc实现的，基测好像没有oc题哎- -

稍微修改一下就好了。主要是算法哈。。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2