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 that you have read and understand our privacy policy and code of conduct.

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