Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.92
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 13:05     Разбить строку на слова из словаря #1
Условие

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

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

Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 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;
}
Тайм лимит на двух тестах. Если лень читать, можете тесты подкинуть?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
23.04.2011, 13:53     Разбить строку на слова из словаря #2
iama, Мб попробуй убрать system("pause")
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 13:57  [ТС]     Разбить строку на слова из словаря #3
asics, когда отправляю на проверку - я его комментю
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.04.2011, 14:31     Разбить строку на слова из словаря #4
Дай плиз ссылку на систему проверки для этой задачи.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 14:33  [ТС]     Разбить строку на слова из словаря #5
ForEveR, http://informatics.mccme.ru/moodle/m...?chapterid=515
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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';
}
Хохол
Эксперт C++
 Аватар для Хохол
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.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
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;
}
Хохол
Эксперт C++
 Аватар для Хохол
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)
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 20:44  [ТС]     Разбить строку на слова из словаря #10
Хохол, подскажите, как оптимально решать эту задачу? саму идею, а то мой рекурсивный обход матрицы явно неоптимален
Хохол
Эксперт C++
 Аватар для Хохол
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;
                  }
    восстанавливаем ответ
}
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 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 минуты
Я, наверно, недопонимаю логику вашего алгоритма, но как он предусматривает тот случай, когда при использовании префикса данной длины, невозможно составить остаток строки?
Хохол
Эксперт C++
 Аватар для Хохол
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]] << ' ';
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
23.04.2011, 21:40  [ТС]     Разбить строку на слова из словаря #14
Хохол, спасибо большое.

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2013, 20:25     Разбить строку на слова из словаря
Еще ссылки по теме:

C++ Разбить строку на слова
Разбить строку на слова C++
Разбить строку на слова, добавить эти слова в массив строк C++

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

Или воспользуйтесь поиском по форуму:
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.
Вложения
Тип файла: txt Input10.txt (6.2 Кб, 21 просмотров)
Yandex
Объявления
30.01.2013, 20:25     Разбить строку на слова из словаря
Ответ Создать тему

Метки
c++, алгоритмы, потестьте, разбиение на слова, Строки
Опции темы

Текущее время: 17:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru