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

Задачка на строки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
07.11.2011, 17:28     Задачка на строки #1
Помогите кто может, пожалуйста.
Задана строка S. Найдите количество ее различных подстрок, включая пустую. Буквы подстроки могут идти не подряд в самой строке.

Ввод
В первой строке записана строка S (длина от 1 до 25).

Вывод
Выведите ответ.

Пример:

Ввод
AAC

Вывод
6
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2011, 17:28     Задачка на строки
Посмотрите здесь:

Задачка на строки C++
задачка про массивом указателей на строки C++
C++ задачка на строки
C++ задачка на строки
C++ Простая задачка: Распаковка строки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.11.2011, 19:07     Задачка на строки #21
-=ЮрА=-, не прокатит тут перебор. Уже для 25 символов будет дико тормозить.


Цитата Сообщение от Alisia Посмотреть сообщение
А как эту задачку можно через динамику решить?
Через префикс-функцию по идее можно. Ну или через хеширование. На e-maxx.ru разбор есть..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
08.11.2011, 19:26  [ТС]     Задачка на строки #22
Цитата Сообщение от diagon Посмотреть сообщение
-=ЮрА=-, не прокатит тут перебор. Уже для 25 символов будет дико тормозить.



Через префикс-функцию по идее можно. Ну или через хеширование. На e-maxx.ru разбор есть..
Это как, через префикс функцию?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.11.2011, 19:28     Задачка на строки #23
http://e-maxx.ru/algo/prefix_function
-=ЮрА=-
09.11.2011, 11:43
  #24

Не по теме:

diagon, вообще число подстрок равно 2*N где N - число символов в строке, я лишь снабдил программу выводом этих подстрок, чтобы можно было доказать это утверждение

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2011, 01:07     Задачка на строки
Еще ссылки по теме:

задачка на строки C++
C++ Задачка на строки (преобразовать множество старых программ для новой версии компилятора)
C++ Задачка на строки.Дана строка, состоящая из слов

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

Или воспользуйтесь поиском по форуму:
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.11.2011, 01:07     Задачка на строки #25
Цитата Сообщение от Alisia Посмотреть сообщение
Это как, через префикс функцию?
Динамикой решается очень просто:
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
#include <iostream>
#include <string>
 
std::string line;
 
int arr[30];
 
int pre_calc (int p = -1)
{
    if (arr[p] != -1 && p > -1)
        return arr[p];
    int res = 1;
    
    for (int i = 0; i < 26; i++)
        for (int j = p + 1; j < line.size(); j++)
            if (line[j] == i + 'A')
            {
                res += pre_calc (j);
                break;
            }
            
            arr[p] = res;
            return res;
}
 
int main ()
{
 
    std::cin >> line;
    for (int i = 0; i < line.size(); i++)
        arr[i] = -1;
    
    std::cout << pre_calc () << std::endl; 
    
    return 0;
}
Yandex
Объявления
13.11.2011, 01:07     Задачка на строки
Ответ Создать тему
Опции темы

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