Одинаковые последовательности в двух строках

#c_sharp #алгоритм

Таких вопросов не мало. Но все, что я нашел ищут либо конкретные куски в строках,
либо просто совпадающие символы.
Вопрос такой. Есть заполненный строками List. В этом листе нужно найти общую для
всех строк часть. НО! Нужно найти не все совпадающие символы, а именно первую совпадающую
часть. 
Например:

QWERTY12345 YU
QWER TY4564 F
QWERGH145
QWER T777
QWE RBT


Результатом такого сравнения должно получится QWE.

Пробовал вот такой штукой.

public static string CommonString(string first, string second)
{
    return new string((first.Intersect(second)).ToArray());
}


Но она, похоже, ищет именно все встречающиеся символы и делает агрегейт, а значит
не подходит.
    

Ответы

Ответ 1

Просто сравнивать все первые символы, потом все вторые и т.д. пока не встретится
хоть один не совпадающий...

Могу набросать на C/C++, C# - не моё...

На C++ что-то типа 

string common(const vector& sts)
{
    for(int i = 0;;++i)
        for(int j = 1; j < sts.size(); ++j)
            if (sts[j-1][i] != sts[j][i])
                return sts[0].substr(0,i);
}


Update С учетом высказанных в комментариях замечаний:

string common(const vector& sts)
{
    if (sts.size() == 0) return "";
    if (sts.size() == 1) return sts[0];
    for(int i = 0;;++i)
    {
        for(int j = 1; j < sts.size(); ++j)
            if (sts[j-1][i] != sts[j][i])
                return sts[0].substr(0,i);
        if (sts[0][i] == 0) return sts[0];
    }
}


Ответ 2

Не претендую на ответ, просто немного переписал алгоритм @Harry на C#:

string Common(List sts)
{
    if (sts.Count <= 1) throw new Exception("sts.Count <= 1");
    var result = "";
    for (int i = 0;; ++i)
    {
        var ok = true;
        for (int j = 1; j < sts.Count; ++j)
        {
            if (sts[j - 1][i] != sts[j][i])
            {
                ok = false;
                break;
            }
        }
        if (ok == false)
        {
            result = sts[0].Substring(0, i);
            break;
        }
    }
    return result;
}


p.s. обязательно обработайте исключения при вызове этого метода в пользовательском коде!



Немного подправил, не обошлось без Linq:

string Common(List sts)
{
    sts = sts.Distinct().ToList();
    if (sts.Count == 0) throw new Exception("sts.Count == 0");
    if (sts.Count == 1) throw new Exception("sts.Count == 1");
    for (int i = 0;;i++)
    {
        for (int j = 1; j < sts.Count; j++)
        {
            try
            {
                if (sts[j - 1][i] != sts[j][i])
                    return sts[0].Substring(0, i);
            }
            catch (IndexOutOfRangeException) { return sts[0].Substring(0, i); }
        }
    }
}




Третий вариант:

string Common(string[] buffer)
{
    var bufferLen = buffer.Length;
    if (bufferLen == 0) throw new Exception("buffer.Length == 0");
    if (bufferLen == 1) throw new Exception("buffer.Length == 1");
    var minStrLen = buffer.Min().Length;
    for (int i = 0; i < minStrLen; i++)
    for (int j = 1; j < bufferLen; j++)
    {
        var str1 = buffer[j - 1];
        var str2 = buffer[j];
        if (str1.Length > i && str2.Length > i)
        {
            if (str1[i] != str2[i]) return buffer[0].Substring(0, i);
        }
        else
        {
            return buffer[0];
        }
    }
    return buffer[0];
}


Ответ 3

http://ideone.com/KgDyXk

using System;
using System.Collections.Generic;

public class Test
{
    static string Common(List strs)
    {
        if (strs == null || strs.Count == 0)
            return "";

        if (strs.Count == 1)
            return strs[0];

        for (int i = 0; i < strs[0].Length; ++i)
            for (int q = 1; q < strs.Count; ++q)
                if (strs[q].Length == i)
                    return strs[q];
                else if (strs[q][i] != strs[q-1][i])
                    return strs[q].Substring(0, i);

        return strs[0];
    }

    public static void Main()
    {
        Console.WriteLine("{1}: {0}", Common(new List()), "");
        Console.WriteLine("{1}: {0}", Common(new List() { "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List() { "a", "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List() { "a", "ab" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List() { "ab", "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List() { "ab", "cd" }), "");
        Console.WriteLine("{1}: {0}", Common(new List() { "ab", "cd", "" }), "");
        Console.WriteLine("{1}: {0}", Common(new List() { "ab", "ab" }), "ab");
        Console.WriteLine("{1}: {0}", Common(new List() { "ab", "ab", "" }), "");
        Console.WriteLine("{1}: {0}", Common(new List() { "abacaba", "aba",
"abacaba" }), "aba");
    }
}


Ответ 4

Решение не претендует на звание оптимального, но зато совсем не громоздкое, плюс
всегда приятно свести решение задачи к одному LINQ запросу :)

public static string FindCommonPrefix(IEnumerable strings)
{
    if (strings == null || !strings.Any())
    {
        return string.Empty;
    }

    var prefix = strings
        .Aggregate((IEnumerable string1, IEnumerable string2) =>
            string1.Zip(string2, (letter1, letter2) => new
            {
                Letter1 = letter1,
                Letter2 = letter2
            })
            .TakeWhile(pair => pair.Letter1 == pair.Letter2)
            .Select(pair => pair.Letter1));

    return string.Join(string.Empty, prefix);
}

...

var prefix = FindCommonPrefix(new List {
    "QWERTY12345 YU",
    "QWER TY4564 F",
    "QWERGH145",
    "QWER T777",
    "QWE RBT",
});

Console.WriteLine(prefix);




Небольшое пояснение:


Приведение типа string к типу IEnumerable осуществляется с целью обеспечения
доступа к отдельным символам строки. В отличие от вызова метода String.ToCharArray
копирования символов не происходит.
Метод Enumerable.Aggregate применяет к последовательности символов агрегатную функцию:


"QWERTY12345 YU", "QWER TY4564 F" → "QWER";
"QWER", "QWERGH145" → "QWER";
...
"QWER", "QWE RBT" → "QWE".

Метод Enumerable.Zip объединяет символы с одинаковым индексом до тех пор, пока не
будет достигнут конец одной из строк. В данном случае используется также метод Enumerable.TakeWhile,
поэтому объединение происходит до тех пор, пока в одной из строк не закончатся символы
либо не станет ложным условие равенства символов.