Учитывая две строки, найдите самый длинный общий мешок символов

Ответ 1

Создайте набор символов, присутствующих в a, и другой символ, присутствующий в b. Пройдите через каждую строку и удалите (например, перепишите с каким-либо иным невозможным значением) все символы, не входящие в набор из другой строки. Найдите самую длинную строку, оставшуюся в каждой (т.е. Самую длинную строку только "неработающих" символов).

Edit: Здесь решение, которое работает примерно так, как указано выше, но с довольно специфичным для языка образом (с использованием локалей/граней С++):

#include <string>
#include <vector>
#include <iostream>
#include <locale>
#include <sstream>
#include <memory>

struct filter : std::ctype<char> {
    filter(std::string const &a) : std::ctype<char>(table, false) {
        std::fill_n(table, std::ctype<char>::table_size, std::ctype_base::space);

        for (size_t i=0; i<a.size(); i++) 
            table[(unsigned char)a[i]] = std::ctype_base::upper;
    }
private:
    std::ctype_base::mask table[std::ctype<char>::table_size];
};

std::string get_longest(std::string const &input, std::string const &f) { 
    std::istringstream in(input);
    filter *filt = new filter(f);

    in.imbue(std::locale(std::locale(), filt));

    std::string temp, longest;

    while (in >> temp)
        if (temp.size() > longest.size())
            longest = temp;
    delete filt;
    return longest;
}

int main() { 
    std::string a = "ABCDDEGF",  b = "FPCDBDAX";
    std::cout << "A longest: " << get_longest(a, b) << "\n";
    std::cout << "B longest: " << get_longest(b, a) << "\n";
    return 0;
}

Edit2: Я считаю, что эта реализация - O (N) во всех случаях (один обход каждой строки). Это основано на std::ctype<char>, используя таблицу для поиска, которая является O (1). С хэш-таблицей результаты поиска также будут иметь ожидаемую сложность O (1), но O (N) наихудший случай, поэтому общая сложность будет ожидаться O (N), но O (N ²) наихудший случай, С набором, основанным на сбалансированном дереве, вы получите O (N lg N) в целом.

Ответ 2

Просто отметим, что эта проблема не допустит "жадного" решения, в котором последовательно создаются большие сумки, расширяя существующие допустимые пакеты по одному элементу за раз. Причина в том, что даже если существует сужающийся мешок длины k, нет необходимости в возможной сумке длины (k-1), как показывает следующий контрпример:

ABCD
CDAB

Понятно, что между двумя строками имеется сумка длиной-4 (A:1, B:1, C:1, D:1), но нет общей сумки длиной 3 мешка. Это говорит о том, что проблема может быть довольно сложной.

Ответ 3

Давайте посмотрим на эту проблему следующим образом.. это решение будет более оптимизировано и будет очень легко кодировать, но прочитать через def, и вы ДОЛЖНЫ прочитать код, чтобы получить эту идею.. иначе это будет просто безумно и сложным

ДУМАЙТЕ ЭТО

в ваших вопросах две строки, которые вы указали, позволяют воспринимать их как два набора, i.e {x, y, z}, символов...

И.. И... ваша результирующая подстрока (набор) будет содержать символы, общие в обеих строках (наборах), и будет непрерывными записями, а квалификационная подстрока (ser) будет иметь значение наибольшее количество записей

приведено несколько свойств результата, но будет работать только при использовании по следующему алгоритму \methodolgy

имеем два множества

a = {BAHYJIKLO}

b = {YTSHYJLOP}

Возьмите

a U b = {-, -, H, Y, J, -, -, L, O}

b U a = {Y, -, -, H, Y, J, L, O, -}

просто, что у меня заменен персонажи, которые не имеют права на объединение set с - "или любым специальным \ignored символ

Таким образом, у нас есть две строки, из которых мы можем легко извлечь HYJ, LO, Y, HYJLO

теперь сравнение строк и подстрок требует времени, так что я делаю это, я пишу эти строки\подстроки в текстовый файл, разделенный пробелом или разными строками.. так что, когда я читаю файл, я получаю всю строку наличия вложенного цикла для поиска подстроки или управления временными переменными....

после того, как у вас есть HYJ, LO, Y, HYJLO, я не думаю, что это проблема, чтобы найти желаемый результат....

ПРИМЕЧАНИЕ:, если вы начинаете обрабатывать строки и подстроки в этом с помощью временных переменных и вложенных циклов, чтобы сначала создать подстроку, затем выполнить поиск... тогда это будет очень дорогостоящее решение... вам нужно использовать такую ​​подачу...

char a[20], b[20]; //a[20] & b[30] are two strings
cin>>a; cin>>b;
int t=0;

open a temporary text file "file1" to write '(built-in-function works here)'
//a U b
for(int x=0; x<length(a); x++)
{
    t=0;

    for(int y=0; y<length(b); x++)
       { if( a[x] == b[y]) t=1; }

    if(t == 1)
       { 
          write 'a[x]' to the file1 '(built-in-function works here)'
          t=0;
       }
    else
       write a 'space' to the file1 '(built-in-function works here)'
}

//b U a
for(int x=0; x<length(a); x++)
{
    t=0;

    for(int y=0; y<length(b); x++)
       { if( b[x] == a[y]) t=1; }

    if(t == 1)
       {
         write 'a[x]' to the file1 '(built-in-function works here)'
         t=0;
       }
    else
       write a 'space' to the file1 '(built-in-function works here)'
}
/*output in the file wil be like this
_____FILE1.txt_____
  HYJ  LO Y HYJLO        
*/
//load all words in an array of stings from file '(built-in-function works here)'

char *words[]={"HYJ","LO","Y","HYJLO"};
int size=0,index=0;

for( int x=0; x<length(words); x++)
    for( int y=0; x<length(words); y++)
    {
       if( x!=y && words[x] is a substring of words[y] ) // '(built-in-function works here)'
          {
               if( length(words[x] ) < size )
               {
                     size = length(words[x];
                     index = x;
               }
          }
    }

 cout<< words[x]; 
 //its the desired result.. its pretty old school bu i think you get the idea

}

Я написал код для... его работы, если вы хотите, чтобы он дал вам электронную почту, я отправлю его вам... b.t.w Мне нравится эта проблема, и сложность этого алгоритма составляет 3n (квадрат)

Ответ 4

Здесь моя довольно анти-pythonic реализация, которая, тем не менее, использует питон замечательно встроенный в множествах и строках.

a = 'ABCDDEGF'
b = 'FPCDBDAX'

best_solution = None
best_solution_total_length = 0

def try_expand(a, b, a_loc, b_loc):
    # out of range checks
    if a_loc[0] < 0 or b_loc[0] < 0:
        return
    if a_loc[1] == len(a) or b_loc[1] == len(b):
        return


    if set(a[a_loc[0] : a_loc[1]]) == set(b[b_loc[0] : b_loc[1]]):
        global best_solution_total_length, best_solution
        #is this solution better than anything before it?
        if (len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]])) > best_solution_total_length:
            best_solution = (a_loc, b_loc)
            best_solution_total_length = len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]])


    try_expand(a, b, (a_loc[0]-1, a_loc[1]), (b_loc[0], b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]+1), (b_loc[0], b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0]-1, b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0], b_loc[1]+1))


for a_i in range(len(a)):
    for b_i in range(len(b)):
        # starts of the recursive expansion from identical letters in two substrings
        if a[a_i] == b[b_i]:
            # if substrings were expanded from this range before then there won't be an answer there
            if best_solution == None or best_solution[0][0] > a_i or best_solution[0][1] <= a_i or best_solution[1][0] > b_i or best_solution[1][1] <= b_i:
                    try_expand(a, b, (a_i, a_i), (b_i, b_i))


print a[best_solution[0][0] : best_solution[0][1]], b[best_solution[1][0] : best_solution[1][1]]

Забыл упомянуть, что это, очевидно, довольно грубый подход, и я уверен, что существует алгоритм, который работает намного быстрее.