Рубрики

Групповая Сдвинутая Строка

Учитывая массив строк (все строчные буквы), задача состоит в том, чтобы сгруппировать их таким образом, чтобы все строки в группе были сдвинутыми версиями друг друга. Две строки S и T называются сдвинутыми, если

S.length = T.length 
and
S[i] = T[i] + K for 
1 <= i <= S.length  for a constant integer K

Например, строки {acd, dfg, wyz, yab, mop} являются сдвинутыми версиями друг друга.

Input  : str[] = {"acd", "dfg", "wyz", "yab", "mop",
                 "bdfh", "a", "x", "moqs"};

Output : a x
         acd dfg wyz yab mop
         bdfh moqs
All shifted strings are grouped together.

Мы можем видеть шаблон среди строк одной группы, разница между последовательными символами для всех символов строки равны. Как в примере выше, возьмите acd, dfg и mop

acd -> 2 1
dfg -> 2 1
швабра -> 2 1

Поскольку различия одинаковы, мы можем использовать это для идентификации строк, принадлежащих к одной группе. Идея состоит в том, чтобы сформировать строку различий в качестве ключа. Если найдена строка с той же разностной строкой, то эта строка также принадлежит к той же группе. Например, вышеупомянутые три строки имеют одинаковую разностную строку, то есть «21».

В приведенной ниже реализации мы добавляем «a» к каждому различию и сохраняем 21 как «ba».

/ * C / C ++ программа для печати групп сдвинутых строк

   вместе. * /

#include <bits/stdc++.h>

using namespace std;

const int ALPHA = 26;   // Всего строчная буква

  
// Метод разностной строки для заданной строки.
// Если строка "adf", то разница будет
// "cb" (сначала разница 3, затем разница 2)
string getDiffString(string str)
{

    string shift = "";

    for (int i = 1; i < str.length(); i++)

    {

        int dif = str[i] - str[i-1];

        if (dif < 0)

            dif += ALPHA;

  

        // Представляем разницу как char

        shift += (dif + 'a');

    }

  

    // Эта строка будет на 1 меньше длины str

    return shift;

}

  
// Метод группировки сдвинутой строки

void groupShiftedString(string str[], int n)

{

    // карта для хранения индексов строки, которые

    // в той же группе

    map< string, vector<int> > groupMap;

    for (int i = 0; i < n; i++)

    {

        string diffStr = getDiffString(str[i]);

        groupMap[diffStr].push_back(i);

    }

  

    // итерация по карте для печати группы

    for (auto it=groupMap.begin(); it!=groupMap.end();

                                                it++)

    {

        vector<int> v = it->second;

        for (int i = 0; i < v.size(); i++)

            cout << str[v[i]] << " ";

        cout << endl;

    }

}

  
// Метод драйвера для тестирования вышеуказанных методов

int main()

{

    string str[] = {"acd", "dfg", "wyz", "yab", "mop",

                    "bdfh", "a", "x", "moqs"

                   };

    int n = sizeof(str)/sizeof(str[0]);

    groupShiftedString(str, n);

    return 0;

}

Выход:

a x
acd dfg wyz yab mop
bdfh moqs

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Групповая Сдвинутая Строка

0.00 (0%) 0 votes