A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© Dreamsky_qihang 中级黑马   /  2015-3-18 11:20  /  1310 人查看  /  15 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

基础测试第十题的找最大子串。题目要求是多个字符串,但我看前辈们都做的是两个字符串的比较。
这个题的要求到底是多个字符串的字串呢?还是两个的就符合要求了?
两个的已经做出来额。多个的花,没有思路啊。

15 个回复

倒序浏览
来人发表一下意见。。我也好有个参考。。
回复 使用道具 举报
:'(没人吗
回复 使用道具 举报
是多个  确实不好做   我看了下好像 效率高点的算法都是很晦涩难道  什么后缀数组 后缀树  自动机什么的
回复 使用道具 举报
有个最笨的方法就是  先找出字符串里面最短的那个   然后在求出其所有的子字符串和其余的去比较  如果是其余的字符串的子串就把子串的长度复制为一个maxlen  然后再循环比较 得到符合条件的子串然后就和求其长度和maxlen比较
回复 使用道具 举报
#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;
}
回复 使用道具 举报
wenfeng340 发表于 2015-3-18 22:07
是多个  确实不好做   我看了下好像 效率高点的算法都是很晦涩难道  什么后缀数组 后缀树  自动机什么的 ...

后面说的这些都不会。这咋整。。
回复 使用道具 举报
wenfeng340 发表于 2015-3-18 22:15
有个最笨的方法就是  先找出字符串里面最短的那个   然后在求出其所有的子字符串和其余的去比较  如果是其 ...

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

这个是多个字符串的吗?待我拷贝下来理解一下:lol
回复 使用道具 举报
没做过这个题
回复 使用道具 举报
Dreamsky_qihang 发表于 2015-3-19 08:46
我一开始的想法也和这差不多。但这个实现起来不现实啊。如果子串的程度够长的话,效率会很低。而且循环也 ...

效率确实很低
回复 使用道具 举报
我基础测试也有这个题目,我只写了两个字符串求最大子串的程序,得分了
回复 使用道具 举报

自测题貌似是需要用c语言来写吧...
回复 使用道具 举报
贾永强 发表于 2015-3-19 11:52
我基础测试也有这个题目,我只写了两个字符串求最大子串的程序,得分了

恩恩。多谢,就是怕给扣了分啊。。自荐信已经很低了。不能在在这扣无谓的分数了
回复 使用道具 举报
楼上那位是oc实现的,基测好像没有oc题哎- -
回复 使用道具 举报
岳挺 发表于 2015-3-19 13:30
楼上那位是oc实现的,基测好像没有oc题哎- -

稍微修改一下就好了。主要是算法哈。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马