Главная » Java, Структуры данных и алгоритмы » Строковые операции

0

В основу любого алгоритма работы с текстом заложены методы обработки символьных строк. Символьные строки представляют основу большого количества источников, включающих научную, лингвистическую, специальную литературу и интернет-приложения. В качестве примера можно привести следующие строки:

Р= "CGTAAACTGCTTTAATCAAACGC" R ="U. S. Men Win Soccer World Cup!"

S = ,,http://www.wiley.com/colledge/cs2java/u.

Первая строка P взята из ДНК-приложения, последняя строка S — интернет-адрес (URL) Web-сайта, а средняя строка R — газетный заголовок. В этом разделе представлено несколько полезных операций, поддерживаемых строковым АТД при обработке строк.

Несколько типичных операций для работы с текстом применяют разделение длинных строк на меньшие. Чтобы можно было оперировать результатами такого разделения, предлагаем использовать термин «подстрока» (substring) строки^ из т символов формата P[i]P[i + 1 ]P[i + 2] …P[j], где 0 < / <у < т – 1, то есть строка, сформированная в Р символами от индекса / до индекса у включительно. В предельном случае это означает, что строка является подстрокой самое себя (при / = 0 и у = т – 1). Если требуется исключить т^кую возможность, следует ограничить определение правильной подстроки требованием, при котором либо / > 0, либо у < т- 1. Для простоты будем использовать P[i…j] для обозначения подстроки строки Р от индекса / до индекса у включительно. Это означает, что

Будем считать, что P[i…j] равна нулевой строке (с длиной 0) при / >у. Чтобы различать особые виды подстрок, будем ссылаться на любую строку формата Р[0…/] при 0 < / < т – 1 как на префикс строки Р, а на строку формата P[i…m – 1] при 0 < / < т – I как на суффикс строки Р. Например, если вернуться к примеру строки Р как строки из ДНК-приложения, то «GGTAA» — это префикс строки Р, «CGC» — суффикс, а «ТТААТС» — (правильная) подстрока строки Р. Заметим, что нулевая строка является префиксом и суффиксом любой строки.

могут быть двух типов: для модификации строк и для получения информации о строке без ее изменения. В Java это разграничение определяется классом String, оперирующим неизменяемой строкой (immutable string), и классом StringBuffer, представляющим изменяемую строку (mutable string).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии