0

Нужно реализовать алгоритм для нахождения закономерностей у элементов строкового массива. Если какой-то символ в слове попадается более чем половине слов, то он записывается в ответ, иначе ставиться "-". Например: массив (ABBACG, ABCCCB, BCBADG, ACCBDG, ACCACG, BCBACC) после обработки алгоритмом должна получиться строка AC-ACG

4
  • Вам что, реализовать алгоритм?
    – Dmitrii
    20 июл 2019 в 18:37
  • Да, нужно реализовать этот алгоритм.
    – Mr. Linsux
    20 июл 2019 в 18:40
  • ваш алгоритм не ясен. Как у вас получилась строка AC-ACG? Почему в ней A и C повторяются? У вас используется 5 символов - ABCDG - где прочерки для символов BDG?
    – tym32167
    20 июл 2019 в 18:54
  • @tym32167 Слова из массива можно мысленно подставить в столбик ровно друг под друга. Потом смотрим: если одна буква повторяется больше половины раз, то она записывается в ответ, иначе ставиться "-"
    – Mr. Linsux
    20 июл 2019 в 19:08

2 ответа 2

2

Можно прогуляться по каждому индексу каждого слова, собрать статистику и сложить в результат.

Например

var words = new[] {"ABBACG", "ABCCCB", "BCBADG", "ACCBDG", "ACCACG", "BCBACC"}; 
var maxLen = words.Max(x=>x.Length);
var sb = new StringBuilder();

for(int i=0; i<maxLen; i++)
{
    var dict = new Dictionary<char, int>();

    for(int j=0; j<words.Length; j++)
    {
        if (i >= words[j].Length) continue;
        var c = words[j][i];
        if (dict.ContainsKey(c)) dict[c]++;
        else dict[c]=1;
    }

    var toInsert = '-';
    foreach(var kv in dict)
    {
        if (kv.Value > (maxLen / 2))
        {
            toInsert = kv.Key;
            break;
        }
    }

    sb.Append(toInsert);
}

Console.WriteLine(sb.ToString());

Вывод

AC-ACG

UPD

Решение с использованием алгоритма Бойера-Мура из соседнего ответа. По скорости работы это то же самое, что первый вариант, но по потреблению памяти будет оптимальней.

var words = new[] { "ABBACG", "ABCCCB", "BCBADG", "ACCBDG", "ACCACG", "BCBACC" };
var maxLen = words.Max(x => x.Length);
var sb = new StringBuilder();

for (int i = 0; i < maxLen; i++)
{
    char major = '-';
    var count = 0;

    for (int j = 0; j < words.Length; j++)
    {
        if (i >= words[j].Length) continue;
        var c = words[j][i];

        if (count == 0)
        {
            major = c;
            count++;
        }
        else if (c == major) count++;
        else count--;
    }

    count = 0;

    for (int j = 0; j < words.Length; j++)
        if (i < words[j].Length)
            if (major == words[j][i]) count++;

    if (count > (maxLen / 2))
        sb.Append(major);
    else
        sb.Append('-');
}

Console.WriteLine(sb.ToString());

Вывод

AC-ACG
1

В дополнение - могу предположить, что инструктор не против увидеть вычисление доминирующих элементов (majority element) с помощью линейного алгоритма Бойера-Мура (это не тот, что подстроки ищет)

Пример реализации на Delphi (символы строк нумеруются с единицы, строки мутабельны, подразумевается, что строи одной длины) выдаёт AC-ACG

function MostCommons(lst: TArray<string>): string;
  var
    len, i, j, half: Integer;
    Counter: TArray<Integer>;
    Sample: string;
  begin
    len := Length(lst[0]);
    Sample := lst[0];
    SetLength(Counter, len + 1);
    for j := 1 to len do
      Counter[j] := 1;

    for i := 0 to High(lst) do begin
      for j := 1 to len do
        if Sample[j] = lst[i][j] then
          Counter[j] := Counter[j] + 1
        else begin
          if Counter[j] > 1 then
            Counter[j] := Counter[j] - 1
          else begin
            Sample[j] := lst[i][j];
            Counter[j] := 1;
          end;
        end;
    end;

    for j := 1 to len do
      Counter[j] := 0;
    for i := 0 to High(lst) do
      for j := 1 to len do
        if lst[i][j] = Sample[j] then
          Inc(Counter[j]);

    half := (Length(lst) + 2) div 2;
    for j := 1 to len do
      if Counter[j] < half then
        Sample[j] := '-';

    Result := Sample;
  end;
2
  • Сорри, я не удержался и запилил версию с этим алгоритмом :) Так что с меня вам плюсик.
    – tym32167
    21 июл 2019 в 14:46
  • Ага, Вы обратный порядок циклов использовали, чтобы одним счётчиком обойтись и строки посимвольно строить билдером. Ну я уже Ваш ответ плюсовал, больше не могу ;)
    – MBo
    21 июл 2019 в 14:55

Ваш ответ

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

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