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

来人发表一下意见。。我也好有个参考。。

:'(没人吗

是多个  确实不好做   我看了下好像 效率高点的算法都是很晦涩难道  什么后缀数组 后缀树  自动机什么的

有个最笨的方法就是  先找出字符串里面最短的那个   然后在求出其所有的子字符串和其余的去比较  如果是其余的字符串的子串就把子串的长度复制为一个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
有个最笨的方法就是  先找出字符串里面最短的那个   然后在求出其所有的子字符串和其余的去比较  如果是其 ...

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

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

int main()

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

没做过这个题

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

效率确实很低

我基础测试也有这个题目，我只写了两个字符串求最大子串的程序，得分了

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

int main()

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

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

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

楼上那位是oc实现的，基测好像没有oc题哎- -

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

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