7

Таких вопросов не мало. Но все, что я нашел ищут либо конкретные куски в строках, либо просто совпадающие символы. Вопрос такой. Есть заполненный строками 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());
}

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

4
  • А совпадать всегда с начала строк будет?
    – pavel
    27 окт 2016 в 6:36
  • Да, в моем случае, совпадать будет с начала строк.
    – Darron
    27 окт 2016 в 6:39
  • Если у меня есть пустая строка - то общих символов ноль? Если есть строка из 1 символа и он не совпадает с первым символом любой другой строки - то общих опять ноль?
    – Monk
    27 окт 2016 в 6:49
  • В последовательности не будет пустых строк. Что до единичного символа - скорее всего, как минимум один символ будет совпадать.
    – Darron
    27 окт 2016 в 6:54

5 ответов 5

5

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

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

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

string common(const vector<string>& 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<string>& 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];
    }
}
1
5

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

string Common(List<string> 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<string> 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];
}
15
  • 1
    мне кажется одна из ветвей не возвращает значения
    – 4per
    27 окт 2016 в 7:38
  • @4per, спасибо, чуть подправил. Странно что студия не выдала ошибку.
    – Align
    27 окт 2016 в 7:41
  • 1
    Хм.. А на строках {"a", "ab"} оно не падает?
    – Qwertiy
    27 окт 2016 в 9:21
  • 1
    catch медленный...
    – Qwertiy
    27 окт 2016 в 10:11
  • 1
    maxStrLen - зачем нам max, если нужен min?
    – Qwertiy
    27 окт 2016 в 11:11
4

http://ideone.com/KgDyXk

using System;
using System.Collections.Generic;

public class Test
{
    static string Common(List<string> 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<string>()), "");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "a", "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "a", "ab" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "a" }), "a");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "cd" }), "");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "cd", "" }), "");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "ab" }), "ab");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "ab", "" }), "");
        Console.WriteLine("{1}: {0}", Common(new List<string>() { "abacaba", "aba", "abacaba" }), "aba");
    }
}
2

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

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

    var prefix = strings
        .Aggregate((IEnumerable<char> string1, IEnumerable<char> 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<string> {
    "QWERTY12345 YU",
    "QWER TY4564 F",
    "QWERGH145",
    "QWER T777",
    "QWE RBT",
});

Console.WriteLine(prefix);

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

  1. Приведение типа string к типу IEnumerable<char> осуществляется с целью обеспечения доступа к отдельным символам строки. В отличие от вызова метода String.ToCharArray копирования символов не происходит.

  2. Метод Enumerable.Aggregate применяет к последовательности символов агрегатную функцию:

    • "QWERTY12345 YU", "QWER TY4564 F" → "QWER";

    • "QWER", "QWERGH145" → "QWER";

    • ...

    • "QWER", "QWE RBT" → "QWE".

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

0
   public static string CommonString(string big, string small)
    {
      string result = string.Empty;

      if (small.Length > big.Length)
      {
        var temp = big;
        big = small;
        small = temp;
      }

      //var res = CommonString("Cisco CISCO3640ATest", "Not3640ANot");
      
      for (int i = 0; i < small.Length; i++)
      {
        StringBuilder sb = new StringBuilder();
        int curi = i;

        for (int j = 0; j < big.Length; j++)
        {
          var stillOk = big[j] == small[curi];
          if (stillOk)
          {
            sb.Append(small[curi]);
            curi++;
          }
          
          if (!stillOk || curi >= small.Length)
          {
            if (result.Length < sb.Length)
            {
              result = sb.ToString();
            }

            sb.Clear();
            curi = i;
          }
        }
      }
      
      return result;
    }
2
  • 1
    Совсем другую задачу решили. 17 фев 2022 в 12:05
  • Ну там у автора как раз с таким смыслом функция используется. И с таким прототипом. Другое дело, что конечную задачу этой функцией может и не стоит решать, но я искал именно такой прототип и наткнулся на эту страницу. Ну и пришлось самому написать. 17 фев 2022 в 13:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.