一道看似简单的找重题难倒了7年开发经验的老程序员和99.9%程序员

futureflsl

题目如下：
请用任意一门编程语言实现如下函数：
输入三个数字文本（文本长度可能不同也可能相同），找出三个数字文本中相同的数字最长组合，且组合后的文本顺序必须在原文本中保持位置不变且长度必须>=2，如果有多个相同长度的组合文本输出一个即可。不满足条件输出为空。例如有以下三个文本
（1）输入132,123,112233则输出为13或者12都可以
（2）输入1523,123,112233则输出为123
（3）输入172853,8516623,053122883则输出为123
（4）输入123,132,321则输出为空
（5）输入123,132,3212则输出为12
（6）输入64532,8366252183,5266435412则输出为652
（7）输入132,123,112233则输出为12或者13，不能是123因为第一个132中3和2顺序必须保持前后关系，也不能是132因为后面都是2在前3在后
我试了很多方法均告失败，确实很难！目前还没方法解决
没看懂？解释一下  就是找出3个文本中数字相同的，并且数字在原来文本位置和组合后的文本保持一致，比如123和132，组合输出为12或者13，其中1和2在原来2个文本中1在前2在后，组合后也要保持这种位置前后关系

woaicrack

这个题好难啊，不会

老东东2019

第五个第六个的输出不是很理解，第五个看最后一个数字，1在3212的第一个2的后面，你输出12是不是不对，第六个也类似

只想划水

我看都看不懂

zorrofox

给个思路，以第五题为例：123,132,3212
A=123
B=132
C=3212  均视为字符串，而非数字
设置长度L>=2，开始计数：

当L=2时，
A={12,23,13}
B={13,12,32}
C={32,21,12,31,22}
用A,B,C的L=2的字符碰撞，可得出 12 or 13

当L=L+1=3时，
A={123}
B={132}
C={321,212,312}
用A,B,C的L=2的字符碰撞，可得出 NULL

当结果=NULL时，上一步L=2的结果为最终解输出，若仍为NULL则循环直至L=2也为NULL时则输出无解。

huzpsb

来自OIer的回复：
LCS水题，dp求解，不会请戳:
http://huzpsb.cf/build/index.php/archives/9/

orcate

题都读不懂

没有裤衩

第一个为什么不是123

longson0662

题目都看不懂......

hlkitty

        static IEnumerable<string> FindSub(string str, int len)
        {
            if (str == null || str.Length < len)
            {
                yield break;
            }
            if (len == 1)
            {
                foreach (var c in str)
                {
                    yield return c.ToString();
                }
                yield break;
            }
            if (len == str.Length)
            {
                yield return str;
                yield break;
            }
            for (int i = 0; i <= str.Length - len; i++)
            {
                var c = str[i];
                foreach (var sub in FindSub(str.Substring(i + 1), len - 1))
                {
                    yield return c + sub;
                }
            }
        }

        static bool Contains(string find, string str)
        {
            if (find == null || str == null || find.Length == 0 || str.Length == 0)
            {
                return false;
            }
            if (find.Length > str.Length)
            {
                return false;
            }
            int cur = 0;
            for (int i = 0; i < find.Length; i++)
            {
                var index = str.IndexOf(find[i], cur);
                if (index < 0)
                {
                    return false;
                }
                cur = index + 1;
            }
            return true;
        }

        static string[] FindMax(string[] array)
        {
            var result = new List<string>();
            if (array == null) { return result.ToArray(); }
            array = array.Where(e => e != null && e.Length >= 2).OrderBy(e => e.Length).ToArray();
            if (array.Length < 2) { return result.ToArray(); }
            var item = array[0];
            for (int newLen = item.Length; newLen >= 2; newLen--)
            {
                foreach (var sub in FindSub(item, newLen))
                {
                    var match = true;
                    for (var index = 1; index < array.Length; index++)
                    {
                        if (!Contains(sub, array[index]))
                        {
                            match = false;
                            break;
                        }
                    }
                    if (match)
                    {
                        result.Add(sub);
                    }
                }
                if (result.Count > 0)
                {
                    return result.ToArray();
                }
            }
            return result.ToArray();
        }

        public static void Main(string[] args)
        {
            var items = @"[
            [""132"",""123"",""112233""],
            [""1523"",""123"",""112233""],
            [""172853"",""8516623"",""053122883""],
            [""123"",""132"",""321""],
            [""123"",""132"",""3212""],
            [""64532"",""8366252183"",""5266435412""],
            [""132"",""123"",""112233""]
            ]";
            var arrays = JsonConvert.DeserializeObject<string[][]>(items);
            foreach (var array in arrays)
            {
                Console.WriteLine($"{string.Join(",", array)} => {string.Join(",", FindMax(array))}");
            }
            Console.ReadLine();
        }