Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
1

Удаление подстрок из строки. Суммировать "вес" удаленных строк

16.03.2012, 01:04. Показов 1239. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Думаю, что задача стандартная, и известна большинству программистам:

Дана строка s, а также набор подстрок, которые можно удалять из этой строки, причем каждая подстрока имеет свой "вес". При удалении подстроки к общему "весу" прибавляется "вес" удаленной подстроки. Нужно по заданной строке и набору найти максимальный вес, который можно набрать, удаляя подстроки из строки.

Например, есть строка abbcca, и заданы такие наборы ( через пробел стоимость подстроки ):
ab 10
bc 20
ca 2
aa 3
Ответом к этим данным есть вес 43 ( 2 раза подряд удаляем bc, потом aa ).

В общем, мне хотелось бы узнать, где можно прочитать про это, или услышать от кого-то алгоритм решения, спасибо!
P.S. Тема точно ДП (динамическое программирование).

Добавлено через 22 минуты
Ап - ап - ап...

Добавлено через 1 час 0 минут
Up up up
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.03.2012, 01:04
Ответы с готовыми решениями:

Удаление подстрок из массива строк
Требуется удалить подстроки из массива строк string. Пробовал через Replase заменить на пустую...

Удаление повторных вхождений подстрок из строк
Помогите пожалуйста исправить ошибку Был скрипт, который удаляет повторные вхождения подстрок в...

Удаление подстрок из строки
Помогите, пожалуйста, с реализацией функции. Есть строка str типа string и строка it типа char....

Удаление несколько подстрок из строки
Есть ли универсальный и легкий вариант для удаление списка подстрок и строки? Число критерий...

10
31 / 31 / 3
Регистрация: 10.05.2011
Сообщений: 120
16.03.2012, 02:02 2
А эти строки Вам откуда нужно получать?
0
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 10:47  [ТС] 3
A eto imeet znachenie? Cherez ifstream pust

Добавлено через 44 минуты
Эх...жду стоящих программистов...

Добавлено через 37 минут
Модераторы, прошу перенести мою тему в подраздел "С++ для экспертов", так как тут никто не знает, как решить этот вопрос, возможно, он не так и прост!

Добавлено через 1 час 2 минуты
Ап в сотый раз...
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.03.2012, 12:33 4
Цитата Сообщение от AncinetHero Посмотреть сообщение
Ап в сотый раз...
ну не совсем в сотый...

Цитата Сообщение от AncinetHero Посмотреть сообщение
или услышать от кого-то алгоритм решения
предложу один алгоритм (может быть есть и лучше). На примере:
Цитата Сообщение от AncinetHero Посмотреть сообщение
Например, есть строка abbcca, и заданы такие наборы ( через пробел стоимость подстроки ):
ab 10
bc 20
ca 2
aa 3
Ответом к этим данным есть вес 43 ( 2 раза подряд удаляем bc, потом aa ).
итак имеем строку: abbcca. Что бы было понятней введу понятие текущие варианты - изначально их нет. Итак перебираем символы из заданной строки:
- символ a . Т.к. текущих вариантов нет, то добавляем к ним только (a, 0) - строка и набранные очки.
- символ b . Перебираем наш текущие варианты и получаем (ab, 0). Проверяем от правого конца строки на наличие такого набора (обязательно от правого конца и необязательно набор должен покрывать всю строку). Такой набор есть, поэтому добавляем к текущим вариантам (, 10) - пустая строка и набранные очки. Итого в текущих вариантах: (ab, 0) и (, 10)
- символ b . Получаем в текущих вариантах: (abb, 0) и (b, 10)
- символ c . Получаем в текущих вариантах: (abbc, 0), из которого получаем еще один (ab, 20). Также получаем (bc, 10) из которого получаем (, 30) . Итого в текущих вариантах имеем: (abbc, 0), (ab, 20), (bc, 10), (, 30).
- символ с . Получаем в текущих вариантах: (abbcc, 0), (abc, 20), из которого получаем еще и (a, 40), получаем (bcc, 10), (c, 30). Итого в текущих вариантах: (abbcc, 0), (abc, 20), (a, 40), (bcc, 10), (c, 30).
- символ a . Получаем: (abbcca, 0) из котрого получаем еще и (abbc, 2), (abca, 20) из которого получаем еще и (ab, 20), (aс, 40) из которого получаем еще и (, 43), (bcca, 10) из которого получаем еще и (bc, 12), (ca, 30) из которого получаем еще и (, 32).
По окончании прохода ищем максимальное число в текущих вариантах. В данном случае это 43.
1
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 13:21  [ТС] 5
Большое спасибо за идею, сейчас попробую реализовать и сдать (есть задача на эту тему).

Но, я не вижу тут динамики, а тема как раз ДП, или она есть?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.03.2012, 13:58 6
Цитата Сообщение от AncinetHero Посмотреть сообщение
или она есть?
есть.
0
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 22:25  [ТС] 7
Где? Здесь обычный цикл, никаких просчетов делать не надо. Тогда задачу "найти сумму чисел в массиве" тоже динамикой можно считать

Добавлено через 8 часов 12 минут
На досуге, пожалуйста, попробуйте проверить этот кусок кода, у меня выдает ошибку в библиотеке STD. В коде ошибку не вижу

Тут C[i].first - подстрока, которую можно удалить, C[i].second - ее стоимость. i = 0..n
COMB[i].first - комбинация(идея поста №4), COMB[i].second - ее стоимость. i = 0..COMB.size()
x - строка размером l ( l=x.length() )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
       vector < pair < string, int > > COMB;
       COMB.push_back( make_pair( "", 0 ) ); // у нас 1 пустая комбинация стоимостью 0
 
       for( i=0; i<l; i++ ){ // идем поочередно по каждому символу строки х
         int size_start = COMB.size(); // сейчас мы будем искать новые комбинации 
              //(см. пост №4) и добавлять их в конец этого же массива, 
              // и потому нужно запомнить начальную границу
 
         for( j=0; j<size_start; j++ ){ //
           COMB[j].first.push_back( X[i] ); // к каждой комбинации добавляем символ строки (за индекс отвечает первый цикл)
 
           for( k=0; k<n; k++ ){ // n - количество заданных подстрок (см. условие)
 
             int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin(); 
             //ищем, есть ли в сочетании с индексом j рассматриваемая подстрока
 
             if( q < COMB[j].first.size() ){ // если есть
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
             // удаляем ее
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
            // проверяем, 
            // не пришли ли мы к такой комбинации раньше
 
                 if( w < COMB[j].first.size() ) // если не пришли
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) ); // добавляем
             }
 
           }
 
         }
 
       }
Добавлено через 8 минут
Ошибку в реализации нашел .. на строке 9 нужно сделать while .. в коде до сих пор нет.

Добавлено через 3 минуты
Может кто то откомпилировать его у себя?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.03.2012, 22:36 8
AncinetHero, весь код покажите.
0
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 22:41  [ТС] 9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
     
main(){
       vector <int> cost( 27, -1 );
       int n, z, i, j, k, l;
       char c;
       string X;
       cin>>n;
       for( i=1; i<=n; i++ ){
            cin>>c>>z;
            cost[ c-'a'+1 ] = z;
       }
       cin>>X;
       l = X.length();
       cin>>n;
       vector < pair < string, int > > C( n+1 );
       for( i=1; i<=n; i++ ){
            cin>>C[i].first;
            for( j=0; j<C[i].first.length(); j++ )
              C[i].second += cost[ C[i].first[j]-'a'+1 ];
       }
       
       vector < pair < string, int > > COMB;
       COMB.push_back( make_pair( "", 0 ) );
       for( i=0; i<l; i++ ){
         int size_start = COMB.size();
         for( j=0; j<size_start; j++ ){\
           COMB[j].first.push_back( X[i] );
           for( k=0; k<n; k++ ){
             int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin();
             if( q < COMB[j].first.size() ){
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
                 if( w < COMB[j].first.size() )
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) );
             }
           }
         }
       }
       for( i=0; i<COMB.size(); i++ )
         cout<<COMB[i].first<<" "<<COMB[i].second<<endl;
         
       system("pause");
     
}
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
16.03.2012, 23:15 10
Начиная отсюда неправильно:
C++
1
2
3
4
5
6
7
        int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin();
             if( q < COMB[j].first.size() ){
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
                 if( w < COMB[j].first.size() )
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) );
я же писал:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
- символ b . Перебираем наш текущие варианты и получаем (ab, 0). Проверяем от правого конца строки на наличие такого набора (обязательно от правого конца и необязательно набор должен покрывать всю строку).
Т.е. например текущий вариант:
(abccnfd, 0). И есть набор cnfd равный 10 (обратите внимание что он до правого конца доходит - это важно). В этом случае в текущие варианты добавится: (abc, 10)

А вот например текущий вариант:
(abccnfd, 0) и есть набор abc равный 10. В этом случае в текущие варианты не добавится ничего (хотя сама подстрока abc присутствует в строке abccnfd, но до правого конца не доходит).
1
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 23:25  [ТС] 11
Нереальный алгоритм) Может и получится написать, но он 100% не оптимальный
0
16.03.2012, 23:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.03.2012, 23:25
Помогаю со студенческими работами здесь

Удаление всех подстрок из строки
Здравствуйте. После выполнения моей программы у меня выдает вот такую ошибку #include...

Обработка строк по условию, получение подстрок из строки! Консультация
Всем доброго времечка! Только начал изучать C#, так что сильно не пинать. Поставил себе для...

С увеличением найденых и соответственно удаленных строк, время удаления строки увеличивается.
Привет всем! Помогите справится с проблемой. Есть Excel таблица. Происходит поиск значений и при...

Обработка строк. Признак окончания ввода строки. Удаление слов из строк
1. Ввести с клавиатуры строку символов. Признак окончания ввода строки - нажатие клавиши &quot;Ввод&quot;....

Удаление подстрок
Здравствуйте! Как можно создать bat файл, решающий следующие задачи: 1)Есть строка:...

Удаление конкретной строки из списка строк, при этом не трогать дублирующие строки
Необходимо из списка удалить конкретную строку, при этом не затронуть дублирующие строки. Как...

Удаление конкретной строки из списка строк, при этом не трогать дублирующие строки
Необходимо из списка удалить конкретную строку, при этом не затронуть дублирующие строки. Как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru