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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Строки. Посчитать, сколько раз входит сочетание, вставить пробел, вычеркнуть все буквы е http://www.cyberforum.ru/cpp-beginners/thread749491.html
1) Дано слово, посчитать, сколько раз входит в него сочетание, скажем, le; 2) Нужно вставить в слове после каждой, стоящей на нечетном месте, пробел; 3) Потом вычеркнуть из слова все буквы e,...
C++ Класс (работа с текстовым файлом) Здравствуйте. помогите пожалуйста) есть класс: #include "stdafx.h" #include <iostream> #include <fstream> #include <stdlib.h> #include <conio.h> #include <string.h> #include <stdio.h> http://www.cyberforum.ru/cpp-beginners/thread749478.html
C++ Циклические программы с регулярной сменой аргумента, содержащие ветвления
Помогите написать программу задачи. Плиз. Вывести на печать значения, удовлетворяют условию y> 1.35 i y <2.4, и соответствующие значения аргумента. Аргумент х изменяется от 0.42 до 0.86 с шагом...
C++ Где применяется bind
Можете пожалуйста привести пример, где boost::bind (или сейчас уже std::bind) необходим и без него не обойтись. Просто, понимаю как работает, но не понимаю где можно применить. Спасибо за ответы.
C++ Бинарное дерево http://www.cyberforum.ru/cpp-beginners/thread749459.html
Объясните пжлст почему не работает программа...при вводе файла пишет -842150451 /*Дан адрес P1 вершины дерева — записи типа TNode, содержащей поля Data (целого типа), Left, Right и Parent (типа...
C++ Файловый ввод-вывод Всем привет. Задание такое: нужно составить программу которая рассчитывает значения полинома и выводит таблицу x-y, при этом записывает результаты в файл txt. Текстовый файл такого формата:... подробнее

Показать сообщение отдельно
Кот Ангенс
317 / 267 / 38
Регистрация: 24.05.2012
Сообщений: 629

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

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