Читать онлайн «Методы и алгоритмы вычислений на строках»

COMPUTING PATTERNS IN STRINGS Bill Smyth McMaster University Curtin University of Technology PEARSON Addison Wesley Harlow, England • London • New York • Boston • San Francisco • Toronto Sydney • Tokyo • Singapore • Hong Kong • Seoul • Taipei • New Delhi Cape Town • Madrid • Mexico City • Amsterdam • Munich • Paris • Milan МЕТОДЫ И АЛГОРИТМЫ ВЫЧИСЛЕНИЙ НА СТРОКАХ Билл Смит Университет Мак-Мастера Университет технологий Кортина Москва • Санкт-Петербург • Киев 2006 ББК 32. 973. 26-018. 2. 75 С50 УДК 681. 3. 07 Издательский дом "Вильяме" Зав. редакцией СИ. Тригуб Перевод с английского Р. Г. Имамутдиновой, канд. физ. -мат. наук А. А. Минько Под редакцией канд. физ. -мат. наук А. А. С50 Методы и алгоритмы вычислений на строках. : Пер. с англ. — М. : ООО "И. Д. Вильяме", 2006. — 496 с. : ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус. ) Книга представляет собой фундаментальное введение в алгоритмы и методы, эффективно вычисляющие паттерны в строковых последовательностях. Речь идет об общих алгоритмах и методах, которые находят применение во многих областях науки и информационных технологий: сжатие данных, криптография, распознавание речи и компьютерное зрение, вычислительная геометрия и молекулярная биология. Рассмотренные в книге алгоритмы предназначены для нахождения в строковых последовательностях определенных типов паттернов — частных, характеристических и внутренних. Каждому типу паттернов посвящена соответствующая часть книги. Книга отличается последовательным изложением материала, большим количеством иллюстративных примеров, свободным обсуждением текущих исследований в этой области, содержит более 500 упражнений, поясняющих и расширяющих материал, изложенный в тексте книги. Книга предназначена для тех, кто имеет достаточную подготовку в математике и информатике и хочет познакомиться с этой интересной и важной областью. Материал книги доступный для студентов старших курсов и аспирантов соответствующих специальностей. ББК 32. 973. 26-018. 2. 75 Вес названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства Addison-Wesley UK. Authorized translation from the English language edition published by Addison Wesley UK, Copyright © 2003. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Russian language edition published by Williams Publishing House according to the Agreement with R&l Enterprises International, Copyright © 2006 ISBN 5 8459 1081 1 (рус. ) © Издательский дом "Вильяме". 2006 ISBN 0 201 39839 7 (англ. ) © Addison-Wesley UK, 2003 ОГЛАВЛЕНИЕ Предисловие 10 Часть I.