Форум программистов, компьютерный форум 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 <time.h> #include <locale.h> #include <iostream>
C++ Не работает функция в С++ Всем привет! Вот мне надо написать функцию, которая находит максимальное среди трёх введённых чисел. Я вот накинул программку и прошу проверить вас... Заранее благодарен! #include <iostream.h> #include <conio.h> float Max(float, float, float) void main() { clrscr(); float max, x1, x2, x3; cout<<"Enter the three numbers\n"; cin>>x1>>x2>>x3; http://www.cyberforum.ru/cpp-beginners/thread281852.html
C++ Считывание файлов в двумерный массив
Всем привет, просьба помочь с кодом. Есть текстовый файл с разными спецсимволами(@, &, *, % и.т.д.) как считать определенные спецсимволы в массив к примеру @ и & а остальные проигнорировать? Заранее спасибо.
Дана строка с набором случайных символов, при вводе 10 букв первые 5 букв становятся большими , вторые 5 букв маленькими C++
Дана строка с набором случайных символов, при вводе 10 букв первые 5 букв становятся большими , вторые 5 букв маленькими .Если непонятно то визуально выглядит так: введите данные: abdtTfgTGY данные изменены: ABDTTfgtgy Именуйте темы осмысленно. Название темы должно максимально полно отражать ее содержимое.
C++ Рекурсия. Перебор различных слагаемых. http://www.cyberforum.ru/cpp-beginners/thread281795.html
Решил изучить рекурсию... Если с факториалом и числами Фибоначчи все просто и понятно, то на первой же задаче я впал в ступор=\ Условие: Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Требуется написать программу, вычисляющую число лесенок, которое можно построить из N кубиков. Входные данные: Во входном файле INPUT.TXT...
C++ Цепь Маркова Мне надо написать программу, которая будет имитировать работу цепи Маркова. Есть ли готовые алгоритмы? В заранее благодарен. подробнее

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

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

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