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

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

Войти
Регистрация
Восстановить пароль
 
Кот Ангенс
317 / 267 / 38
Регистрация: 24.05.2012
Сообщений: 629
#1

Строковый алгоритм - C++

29.12.2012, 12:00. Просмотров 397. Ответов 3
Метки нет (Все метки)

Помогите, пожалуйста, найти алгоритм (само решение писать не надо). Задача такова:
Дан текст и список правил замены. Каждое правило заменяет одну или несколько букв текста на одну или несколько других букв. Требуется определить, есть ли в правилах зацикливания, и, если есть, вывести их все (или, в крайнем случае, одно любое). Если же нет, нужно произвести замены в тексте. Например:
ababb
ab -> cd
cdcd -> a
На выходе должно получиться cd (ababb -> cdabb -> cdcdb -> ab -> cd). Несколько примеров с циклами:
b -> abc
d -> e
e -> f
f -> d
Предполагается, что количество правил в большинстве случаев не превышает 100, причем большая часть из них заменяет ровно одну букву на одну или несколько других. Длина текста не превышает 100 000 символов.
Каждый символ кодируется четырьмя байтами.

Как определить циклы, я примерно понимаю - составить граф и обойти его. Если попали туда, где уже были - значит, цикл. Но вот с заменами хуже - хотелось бы сделать все за наименьшее количество проходов по строке.

Добавлено через 11 минут
Цитата Сообщение от Кот Ангенс Посмотреть сообщение
Каждое правило заменяет одну или несколько букв текста на одну или несколько других букв.
Поправка, на ноль или более букв.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2012, 12:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Строковый алгоритм (C++):

Дан строковый файл. Создать новый строковый файл, содержащий все строки исходного файла наименьшей длины (в том же порядке). - C++
Даны имена двух файлов вещественных чисел. Известно, что первый из них существует и является непустым, а второй в текущем каталоге...

Строковый массив (объявить пустой глобальный строковый массив из 16 элементов) - C++
Подскажите, как объявить пустой глобальный строковый массив из 16 элементов? в качестве элементов будут указаны пути к графическим...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Строковый калькулятор - C++
добрый вечер. мне нужно написать программу, выполняющую функцию строкового калькулятора с операциями+-*/. Нашла исходники, но там помимо...

Строковый литерал - C++
Вопрос к профи: Верно ли что, когда мы инициализирум строку вот так: const char *str = "Строка", то компилятор понимает ее так: 1) char...

Строковый анализатор - C++
Подскажите почему код выдает всякий мусор, подает звуковые сигналы Должен работать так: Если введешь так: "11/23/34" или "11.23.34"...

3
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
29.12.2012, 12:03 #2
я правильно понял, что у тебя есть несколько слов, которые нужно заменить на другие слова и текст, где это нужно сделать?
0
Кот Ангенс
317 / 267 / 38
Регистрация: 24.05.2012
Сообщений: 629
29.12.2012, 12:10  [ТС] #3
Ну, если последовательность символов назвать словом, то да.
0
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
29.12.2012, 12:13 #4
аа ...
префиксное дерево ...
смотри еще http://en.wikipedia.org/wiki/Aho%E2%...hing_algorithm
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2012, 12:13
Привет! Вот еще темы с ответами:

Строковый файл - C++
Дан строковый файл, содержащий даты в формате «день/месяц/год», причем под день и месяц отводится по две позиции, а под год — четыре...

Строковый класс - C++
Ребят, помогите решить пожалуйста... Написать программу для работы с строковым классом. В классе предусмотреть все основные операции...

Строковый ввод-вывод - C++
1) Скопировать из файла F1 в файл F2 строки, начиная с N до K. 2) Подсчитать количество согласных букв в файле F2. заранее...

Строковый ввод-вывод - C++
Помогите пожалуйста решить задачу, вот она: Нужно создать текстовый файл F1 не менее, чем из 10 строк и записать в него информацию ...


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
29.12.2012, 12:13
Ответ Создать тему
Опции темы

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