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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Стеки http://www.cyberforum.ru/cpp-beginners/thread281855.html
Помогите разобраться со стеками.Вылетает 3 ошибки при компеляции. #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> #include <math.h> #include <fstream> #include...
C++ Не работает функция в С++ Всем привет! Вот мне надо написать функцию, которая находит максимальное среди трёх введённых чисел. Я вот накинул программку и прошу проверить вас... Заранее благодарен! #include <iostream.h>... http://www.cyberforum.ru/cpp-beginners/thread281852.html
C++ Считывание файлов в двумерный массив
Всем привет, просьба помочь с кодом. Есть текстовый файл с разными спецсимволами(@, &, *, % и.т.д.) как считать определенные спецсимволы в массив к примеру @ и & а остальные проигнорировать? ...
Дана строка с набором случайных символов, при вводе 10 букв первые 5 букв становятся большими , вторые 5 букв маленькими C++
Дана строка с набором случайных символов, при вводе 10 букв первые 5 букв становятся большими , вторые 5 букв маленькими .Если непонятно то визуально выглядит так: введите данные: abdtTfgTGY...
C++ Рекурсия. Перебор различных слагаемых. http://www.cyberforum.ru/cpp-beginners/thread281795.html
Решил изучить рекурсию... Если с факториалом и числами Фибоначчи все просто и понятно, то на первой же задаче я впал в ступор=\ Условие: Лесенкой называется набор кубиков, в котором каждый более...
C++ Цепь Маркова Мне надо написать программу, которая будет имитировать работу цепи Маркова. Есть ли готовые алгоритмы? В заранее благодарен. подробнее

Показать сообщение отдельно
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297

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

23.04.2011, 13:05. Просмотров 3397. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru