Матч 409, Упорядоченная суперстрока (OrderedSuperString)

Дивизион 2, Уровень 2

Строка x является упорядоченной надстрокой для множества слов words, если:

· Каждое слово из words является подстрокой x;

· Существует такая последовательность индексов x₁ ≤ x₂ ≤ … ≤ x_n, что слово words[i] начинается в с позиции x_i. Массив words содержит n слов.

Например, “abca” является упорядоченной надстрокой для {“abc”, “ca”}, а “cabc” нет.

По заданному массиву слов words найти длину кратчайшей упорядоченной надстроки.

Класс: OrderedSuperString

Метод: int getLength(vector<string> words)

Ограничения: words содержит от 1 до 50 строк, каждая из которых состоит из букв ‘a’ – ‘z’.

Вход. Множество слов words.

Выход. Длина кратчайшей упорядоченной надстроки для множества слов words.

Пример входа

words

{"abc","ca"}

{"a","a","b","a"}

{"abcdef", "ab","bc", "de","ef"}

Пример выхода

4

3

6

РЕШЕНИЕ

обработка строк

Проходим по массиву слов words. Будем располагать каждое из слов words[i] как можно левее. В переменной LastPos храним индекс самой левой позиции, в которой можно расположить words[i]. В переменной j перебираем все допустимые позиции, с которой может начинаться слово words[i]. Длину общей части результирующей строки res и words[i] храним в OverlapLength. Общую часть res и words[i] заносим соответственно в строки a и b. Если a = b, то увеличиваем res, приклеивая справа суффикс words[i], начинающийся с позиции OverlapLength. Если OverlapLength больше длины words[i], то к res ничего не добавляется.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

class OrderedSuperString

{

public:

int getLength(vector<string> words)

{

string a, b, res;

int i, j, OverlapLength, LastPos = 0;

for(i = 0; i < words.size(); i++)

{

for(j = LastPos; j <= res.size(); j++)

// try to put words[i] at position j that begins

// not earlier than LastPos

{

// length of overlapping part res & words[i]

OverlapLength = min(words[i].size(),res.size() - j);

a = res.substr(j,OverlapLength);

b = words[i].substr(0,OverlapLength);

// if Overlapping parts of res & words[i] are equal

if (a == b)

{

res = res + words[i].substr(OverlapLength);

LastPos = j;

break;

}

}

}

return res.size();

}

};