С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.92
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
#1

Разбить строку на слова из словаря - C++

23.04.2011, 13:05. Просмотров 3477. Ответов 14

Условие

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

Формат входных данных

Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.

Формат выходных данных

Выведите Васин текст с пробелами между словами (пробел после последнего слова допустим). Если возможно несколько вариантов разбиения строки на слова, выведите любой их них. Гарантируется, что хотя бы один способ разбиения строки на словарные слова существует.


Я решал так - строил матрицу, в которой неотрицательное значение элемента, означает номер словарного слова, которое содержится в разбиваемой строке с i-го по j-ый символ. Потом рекурскивно находил нужную последовательность в матрице.

Решение

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
 
using namespace std;
using std::string;
 
vector <string> dict;
stack <int> res;
int dict_len, a[1000][1000];
bool happy_end;
 
void parse(int st, int en, int row)
{
    bool profit = false;
 
    if (!happy_end)
    {
        for (int i = st; i <= en && !happy_end; i++)
            if (a[i][row] != -1)
            {
                profit = true;
                res.push(a[i][row]);
                if (i == en)
                {
                    happy_end = true;
                    break;
                }
                else
                    parse(i + 1, en, row + i - st + 1);
            }
 
        if (!profit) res.pop();
    }
}
 
int main()
{
  string base, ts;
  int i, j, pos;
 
  cin >> base >> dict_len;
 
  for (i = 0; i < 1000; i++)
    for (j = 0; j < 1000; j++)
      a[i][j] = -1;
 
  for (i = 0; i < dict_len; i++)
  {
    cin >> ts;
    dict.push_back(ts);
    pos = -1;
    while ((pos = base.find(ts, pos + 1)) != string::npos)
    {
      a[pos + ts.length() - 1][pos] = i;
    }
  }
 
  if (base == "")
    return 0;
 
  happy_end = false;
 
  parse(0, base.length() - 1, 0);
 
  ts = "";
 
  while (!res.empty())
  {
    ts = dict[res.top()] + ' ' + ts;
    res.pop();
  }
 
  cout << ts << endl;
 
  system("pause");
 
  return 0;
}
Тайм лимит на двух тестах. Если лень читать, можете тесты подкинуть?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2011, 13:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разбить строку на слова из словаря (C++):

Строка: Строку разбить на слова и слова запихнуть в массив char. - C++
Вобщем пока нужно: 1) строку разбить на слова и слова запихнуть в масив char. но у меня почему то вообще не то записывает в масив, хоча...

Разбить строку на слова, добавить эти слова в массив строк - C++
Привет всем! Понадобилось решить одну простенькую задачку: Разбить строку на слова, добавить эти слова в массив строк, вывести...

Строку разбить на слова и слова запихнуть в масив char - C++
Вобщем пока нужно: 1) строку разбить на слова и слова запихнуть в масив char. но у меня почему то вообще не то записывает в масив, хоча...

Разбить строку на слова - C++
Здравствуйте! Решаю задачу, надо разбить предложение на слова с помощью функции strtok. Делаю вот так но не уверен что это правильно....

Разбить строку на слова - C++
Добрый день. Есть массив char (say), в него вводят строку (два-три слова) с пробелами и без пробела в конце. Цикл разбивает её на отдельные...

Разбить строку на слова - C++
Разбить строку на слова. Все слова записать в отдельную строку. Помогите пожалуйста не получается. #include &lt;iostream&gt; #include...

14
asics
Freelance
Эксперт С++
2850 / 1785 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
23.04.2011, 13:53 #2
iama, Мб попробуй убрать system("pause")
0
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 13:57  [ТС] #3
asics, когда отправляю на проверку - я его комментю
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
23.04.2011, 14:31 #4
Дай плиз ссылку на систему проверки для этой задачи.
0
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 14:33  [ТС] #5
ForEveR, http://informatics.mccme.ru/moodle/m...?chapterid=515
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
23.04.2011, 14:56 #6
Написал так - ибо думать лень. Проходит только 2 теста. Хех)

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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
 
int main()
{
    std::vector<std::string> vec;
    std::string str;
    std::cin >> str;
    int N = 0;
    std::cin >> N;
    std::string tmp;
    vec.reserve(N);
    for(int i=0; i<N; ++i)
    {
        std::cin >> tmp;
        vec.push_back(tmp);
    }
    std::string res;
    for(std::vector<std::string>::iterator iter = vec.begin();
        iter != vec.end(); )
    {
        if(str.empty())
            break;
        size_t idx  = str.find(*iter);
        if(idx != std::string::npos)
        {
            res += std::string(str.begin() + idx, str.begin() + idx + iter->size()) + ' ';
            str.erase(str.begin() + idx, str.begin() + idx + iter->size());
        }
        else
            ++iter;
    }
    std::cout<<res;
    std::cout<<'\n';
}
1
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
23.04.2011, 19:45 #7
iama, да вы человек-обфускатор. Долго же я пытался понять, чем отличается st от row.
При первом вызове st == row, значит всегда i + 1 == row + i - st + 1.
1
asics
Freelance
Эксперт С++
2850 / 1785 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
23.04.2011, 19:50 #8
Пытался тоже зделать, дальше 5-го теста не идет
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
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>
#include <numeric>
 
typedef std::string  T_str;
 
bool comp(T_str a, T_str b){
  return a.length() > b.length();
}
 
int main(){
  std::ifstream  ifs("input.txt");
  T_str  main_str, res_str;
  getline(std::cin, main_str);
  res_str = main_str;
  const size_t  &N = std::cin.get() - '0';
  std::vector<T_str>  dict_words(N), tail;
  for(size_t i = 0; i < N; ++i)
    std::cin >> dict_words[i];
  std::sort(dict_words.begin(), dict_words.end(), comp);
  for(size_t i = 0; i < N; ++i){
    while(main_str.find(dict_words[i]) != T_str::npos){
      tail.push_back(dict_words[i]);
      main_str.erase(main_str.find(dict_words[i]), dict_words[i].length());
    }
  }
  if(!main_str.empty())
    tail.push_back(main_str);
  std::sort(tail.begin(), tail.end());
  bool key = false;
  do{
    T_str tmp = std::accumulate(tail.begin(), tail.end(), T_str(""));
    if(tmp == res_str){
      std::copy(tail.begin(), tail.end(), std::ostream_iterator<T_str>(std::cout, " "));
      key = true;
      break;
    }
  }while(std::next_permutation(tail.begin(), tail.end()));
  if(!key)
    std::cout << res_str;
  return 0;
}
1
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
23.04.2011, 20:25 #9
iama, для начала, у вас WA.
Код
aab
3
a
aa
aab
Добавлено через 22 минуты
Когда разберетесь с WA, запустите например такой тест:
Код
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
4
b
ba
aa
aaaa
(b + 99a)
2
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 20:44  [ТС] #10
Хохол, подскажите, как оптимально решать эту задачу? саму идею, а то мой рекурсивный обход матрицы явно неоптимален
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
23.04.2011, 20:59 #11
У вас решение работает за экспоненциальное время.
Если какой-то префикс исходного слова можно составить многими способами, ваше решение в худшем случае будет перебирать все эти способы. Но нам не нужны сами способы, нам достаточно знать для каждого префикса, можно ли его составить из слов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool can[1000];
int how[1000];
int main()
{
     can[0] = true;
     how[0] = -1;
     for(int i = 0; i < base.size(); i++)
         if(can[i])
             for(int j = 0; j < words.size(); j++)
                  if(base.substr(i,words[j].size()) == words[j])
                  {
                       can[i+words[j].size()] = true;
                       how[i+words[j].size()] = j;
                  }
    восстанавливаем ответ
}
1
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 21:25  [ТС] #12
Хохол, спасибо огромное. Насколько я понял, в how лежит индекс слова, которое может предварять остальную часть строки, вывод реализовывал так:

C++
1
2
3
4
5
6
7
    int pos = 1;
 
    while (pos <= base.length())
    {
        cout << words[how[pos]] << ' ';
        pos += words[how[pos]].length();
    }
на обоих ваших тестах работает неправильно. Что я не так делаю?

Добавлено через 2 минуты
Я, наверно, недопонимаю логику вашего алгоритма, но как он предусматривает тот случай, когда при использовании префикса данной длины, невозможно составить остаток строки?
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
23.04.2011, 21:33 #13
how[i] - индекс слова, оканчивающегося (i-1)-ым символом.
Ответ восстанавливать с конца:
C++
1
2
3
4
5
6
7
8
9
int pos = base.size();
vector<int> ans;
while(pos > 0)
{
    ans.push_back(how[pos]);
    pos -= words[how[pos]].size();
}
for(int i = ans.size()-1; i >= 0; i--)
    cout << words[ans[i]] << ' ';
1
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 21:40  [ТС] #14
Хохол, спасибо большое.

Не по теме:

а я - безнадежен

0
zverek56
0 / 0 / 0
Регистрация: 30.01.2013
Сообщений: 3
30.01.2013, 20:25 #15
Здравствуйте)
Решаю ту же задачу, но на Delphi.
Не проходит лишь 10 тест. Какая-то внутренняя ошибка программы. Весь день просидел, а понять в чём дело не могу.

Вот полный код. Тест вложен.
Delphi
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
program inf;
 
{$APPTYPE CONSOLE}
 
type
  slova = record                  //тип, содержащий слова с определённым количеством букв
    s: array [1..2005] of string; //сами слова
    k: integer;                   //количество слов с данным количеством букв
  end;
 
var
  m: array [1..25] of slova;     //индекс соответствует количеству букв
  str, st: string;
  N, i, j: integer;
  ok: boolean;
 
function sr(str: string): boolean;   //проверяет наличие слова в словаре
var
  i: integer;
begin
  sr:=false;
  with m[length(str)] do
    for i:=1 to k do
      if (s[i]=str) then
        begin
          sr:=true;
          break;
        end;
end;
 
function f(str: string): string;     //рекурсивная функция, при первом удачном окончании, т.е. символов не осталось, возвращает значение
var
  i: integer;
  st, st1: string;
begin
  //writeln(str);
  st:=''; st1:='';
  for i:=1 to length(str) do
    if (not ok) then
      begin
        st:=st+str[i];
        if sr(st) then
          begin
            //writeln(st);
            st1:=str;
            delete(st1, 1, i);
            if (st1<>'') then f:=st+' '+f(st1)
            else begin ok:=true; f:=st end;
          end;
      end;
end;
 
begin
  //assign(input, 'File1.txt'); reset(input);
  //assign(output, 'File2.txt'); rewrite(output);
  readln(str);
  readln(N);
  for i:=1 to 20 do m[i].k:=0;
  for i:=1 to N do          //сортируем слова в словаре по количеству букв
    begin
      readln(st);
      with m[length(st)] do
        begin
          inc(k);
          s[k]:=st;
        end;
    end;
  ok:=false;
  writeln(f(str));
end.
0
Вложения
Тип файла: txt Input10.txt (6.2 Кб, 23 просмотров)
30.01.2013, 20:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2013, 20:25
Привет! Вот еще темы с ответами:

Разбить введенную строку на слова - C++
Да, я знаю, что тема не нова и много раз поднималась на этом форуме.=-O Но не могли бы вы максимально понятно и просто реализовать эту...

Разбить строку на слова, удвоить пробелы - C++
Всем привет,такая проблема,не работает в программе 1 функция,2-3 работают вроде..Помогите Пожалуйста исправить код или как сделать легче...

Как считать строку и разбить ее на слова? - C++
Задача на С. (стандарт) Необходимо считать строку и разбить ее на слова (слова разделены пробелами (не меннее одного)). Количество слов и...

Разбить входную строку, состоящую из трех слов, на слова - C++
Нужно написать программу, которая записывает входную строку состоящюю из трех слов в три разных(по слову в каждую) строки. Желательно без...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.