Length s2 n2 1 зачем нужно

Строки

Мы уже рассматривали строки как простой тип данных наряду с целыми и вещественными числами и знаем, что строка – это последовательность символов, заключенных в одинарные или двойные кавычки.

В Python нет символьного типа – типа данных, объектами которого являются одиночные символы. Однако язык позволяет рассматривать строки как объекты, состоящие из подстрок длинной в один и более символов. При этом, в отличие от списков, строки не принято относить к структурам данных. Видимо потому, что структуры данных состоят из более простых типов данных, а для строк в Python нет более простого (символьного) типа.

С другой стороны, строка, как и список, – это упорядоченная последовательность элементов. Следовательно, из нее можно извлекать отдельные символы и срезы.

>>> s = "Hello, World!" >>> s[0] 'H' >>> s[7:] 'World!' >>> s[::2] 'Hlo ol!'

В последнем случае извлечение идет с шагом, равным двум, то есть извлекается каждый второй символ. Извлекать срезы с шагом также можно из списков.

Важным отличием от списков является неизменяемость строк в Python. Нельзя перезаписать какой-то отдельный символ или срез в строке:

>>> s[-1] = '.' Traceback (most recent call last): File "", line 1, in TypeError: 'str' object does not support item assignment

Интерпретатор сообщает, что объект типа str не поддерживает присвоение элементам.

Если требуется изменить строку, то можно создать новую из срезов старой:

>>> s = s[0:-1] + '.' >>> s 'Hello, World.'

В примере берется срез из исходной строки, соединяется с другой строкой. Получается новая строка, которая присваивается переменной s . Ее старое значение при этом теряется.

Методы строк

В Python для строк есть множество методов. Посмотреть их можно по команде dir(str) , получить информацию по каждому – help(str.имя_метода) . Рассмотрим наиболее интересные из них.

Методы split() и join()

Метод split() позволяет разбить строку по пробелам. В результате получается список слов. Если пользователь вводит в одной строке ряд слов или чисел, каждое из которых должно в программе обрабатываться отдельно, то без split() не обойтись.

>>> s = input() red blue orange white >>> s 'red blue orange white' >>> sl = s.split() >>> sl ['red', 'blue', 'orange', 'white'] >>> s 'red blue orange white'

Список, возвращенный методом split() , мы могли бы присвоить той же переменной s , то есть s = s.split() . Тогда исходная строка была бы потеряна. Если она не нужна, то лучше не вводить дополнительную переменную.

Метод split() может принимать необязательный аргумент-строку, указывающей по какому символу или подстроке следует выполнить разделение:

>>> s.split('e') ['r', 'd blu', ' orang', ' whit', ''] >>> '40030023'.split('00') ['4', '3', '23']

Метод строк join() выполняет обратное действие. Он формирует из списка строку. Поскольку это метод строки, то впереди ставится строка-разделитель, а в скобках — передается список:

>>> '-'.join(sl) 'red-blue-orange-white'

Если разделитель не нужен, то метод применяется к пустой строке:

>>> ''.join(sl) 'redblueorangewhite'

Методы find() и replace()

Данные методы строк работают с подстроками. Методы find() ищет подстроку в строке и возвращает индекс первого элемента найденной подстроки. Если подстрока не найдена, то возвращает -1.

>>> s 'red blue orange white' >>> s.find('blue') 4 >>> s.find('green') -1

Поиск может производиться не во всей строке, а лишь на каком-то ее отрезке. В этом случае указывается первый и последний индексы отрезка. Если последний не указан, то ищется до конца строки:

>>> letters = 'ABCDACFDA' >>> letters.find('A', 3) 4 >>> letters.find('DA', 0, 6) 3

Здесь мы ищем с третьего индекса и до конца, а также с первого и до шестого. Обратите внимания, что метод find() возвращает только первое вхождение. Так выражение letters.find(‘A’, 3) последнюю букву ‘A’ не находит, так как ‘A’ ему уже встретилась под индексом 4.

Метод replace() заменяет одну подстроку на другую:

>>> letters.replace('DA', 'NET') 'ABCNETCFNET'

Исходная строка, конечно, не меняется:

>>> letters 'ABCDACFDA'

Так что если результат надо сохранить, то его надо присвоить переменной:

>>> new_letters = letters.replace('DA', 'NET') >>> new_letters 'ABCNETCFNET'

Метод format()

Строковый метод format() уже упоминался при рассмотрении вывода на экран с помощью функции print() :

>>> print("This is a . It's .".format("ball", "red")) This is a ball. It's red.

Однако к print() он никакого отношения не имеет, а применяется к строкам. Лишь потом заново сформированная строка передается в функцию вывода.

Возможности format() широкие, рассмотрим основные.

>>> s1 = "length - <>, width - <>, height - <>" >>> s1.format(3, 6, 2.3) 'length - 3, width - 6, height — 2.3'

Если фигурные скобки исходной строки пусты, то подстановка аргументов идет согласно порядку их следования. Если в фигурных скобках строки указаны индексы аргументов, порядок подстановки может быть изменен:

>>> s2 = "height - , length - " >>> s2.format(3, 6) 'height - 6, length - 3'

Кроме того, аргументы могут передаваться по слову-ключу:

>>> info = "This is a . It's ." >>> info.format(subj="table", prop="small") "This is a table. It's small."

Пример форматирования вещественных чисел:

>>> " ".format(3.33333, 10/6) '1.67 3.333'

Практическая работа

Вводится строка, включающая строчные и прописные буквы. Требуется вывести ту же строку в одном регистре, который зависит от того, каких букв больше. При равном количестве преобразовать в нижний регистр. Например, вводится строка «HeLLo World», она должна быть преобразована в «hello world», потому что в исходной строке малых букв больше. В коде используйте цикл for , строковые методы upper() (преобразование к верхнему регистру) и lower() (преобразование к нижнему регистру), а также методы isupper() и islower() , проверяющие регистр строки или символа.
Строковый метод isdigit() проверяет, состоит ли строка только из цифр. Напишите программу, которая запрашивает с ввода два целых числа и выводит их сумму. В случае некорректного ввода программа не должна завершаться с ошибкой, а должна продолжать запрашивать числа. Обработчик исключений try-except использовать нельзя.

Примеры решения и дополнительные уроки в pdf-версии курса

X Скрыть Наверх

Python. Введение в программирование

Shortest Common Superstring Problem

Проблема кратчайшей общей надстроки формулируется следующим образом: найти кратчайшую строку, такую, что каждая строка из заданного набора являлась бы её подстрокой. Эта проблема имеет место как в биоинформатике (задача сборки генома в общем случае) так и в сжатии данных (вместо данных хранить их надстроку и последовательность пар, вида (индекс вхождения, длина)).

Когда я искал в сети информацию по этой проблеме и её решению на русском языке — находилась лишь пара постов про биоинформатике, где вскользь упоминаются эти слова. Кода (кроме жадного алгоритма), конечно же, тоже не было. Разобравшись в проблеме, этот факт сподвиг на статью здесь.

Осторожно, 4 мегабайта!

По большей части, статья — попытка перевести на понятный язык, проиллюстрировать, приправить примером, и, конечно же, реализовать на Java 4-приближённый алгоритм конструирования надстроки из книжки Дэна Гасфилда (см. использованную литературу). Но сначала небольшое введение и 2-приближенный, жадный алгоритм.

В простейшем случае (если бы в названии проблемы не было слова “кратчайшей”) решением задачи будет простое конкатенирование входных строк в произвольном порядке. Но при данной постановке проблемы мы имеем дело с NP-полнотой, что означает, что в настоящее время не существует алгоритма, с помощью которого можно было бы решить эту задачу на машине Тьюринга за время, не превосходящее полинома от размера данных.

Ввод: S₁, S₂, …, S_n — множество строк конечного алфавита E*.
Вывод: X — строка алфавита E* содержащая каждую строку S_1..n в качестве подстроки, где длина |X| минимизирована.

Пример. Возьмём множество строк S = . В случае с конкатенированием длина выходной надстроки будет 9 (X = abccdeeab), что, очевидно, не лучший вариант, так как строки могут иметь суффиксно-префиксное совпадение. Длину этого совпадения мы будем называть overlap. (Выбор английского слова произведён неслучайно, так как конкретного и однозначного перевода на русский язык оно не имеет. В русскоязычной литературе обычно используются термины наложение, пересечение, перекрытие и суффиксно-префиксное совпадение).

Отступление. Понятие overlap является одним из важнейших в процессе реализации алгоритмов конструирования надстрок. Вычисление overlap’a для упорядоченной пары строк (S_i, S_j) сводится к нахождению длины максимального совпадения суффикса строки S_i с префиксом строки S_j.

Один из способов запрограммировать нахождение overlap’a представлен в следующем листинге.

 /* * Функция вычисляет максимальную длину суффикса строки s1 * совпадающего с префиксом строки s2 (длину наложения s1 на s2) */ private static int overlap(String s1, String s2) < int s1last = s1.length() - 1; int s2len = s2.length(); int overlap = 0; for (int i = s1last, j = 1; i >0 && j < s2len; i--, j++) < String suff = s1.substring(i); String pref = s2.substring(0, j); if (suff.equals(pref)) overlap = j; >return overlap; >

Возврат к примеру. Если конкатенировать строки S = с учётом их overlap’ов, то получим строку X = abcdeab с длиной 7, которая короче предыдущей, но не самая короткая. Самая короткая строка получится при конкатенировании строк с учётом overlap’ов в порядке 3-1-2, тогда результирующая строка X = eabcde будет иметь длину 6. Таким образом, мы свели задачу к нахождению оптимального порядка конкатенирования строк с учётом их overlap’ов.

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

Жадный алгоритм

В этом алгоритме на каждой итерации мы пытаемся найти максимальный overlap двух любых строк и слить их в одну. Мы надеемся, что результат этого алгоритма будет близко приближён к фактически оптимальному.

1. Пока S содержит более одной строки, находим две строки с максимальным overlap’ом и сливаем их в одну (например, ABCD + CDEFG = ABCDEFG).
2. Возвращаем одну оставшуюся в S строку.

Пример реализации этого алгоритма представлен в следующем листинге.

 /* * Функция сливает строки с максимальным наложением до тех пор, * пока не останется единственная строка (общая надстрока). */ public static String createSuperString(ArrayList strings) < while (strings.size() >1) < int maxoverlap = 0; String msi = strings.get(0), msj = strings.get(1); for (String si : strings) for (String sj : strings) < if (si.equals(sj)) continue; int curoverlap = overlap(si, sj); if (curoverlap >maxoverlap) < maxoverlap = curoverlap; msi = si; msj = sj; >> strings.add(merge(msi, msj, maxoverlap)); strings.remove(msi); strings.remove(msj); > return strings.get(0); >

В этом листинге появилась другая простая функция merge, которая сливает две строки в одну с учётом их overlap’a. Так как последний уже был вычислен, логично просто передать его в качестве параметра.

 /* * Функция сливает строки s1 и s2 на длину len, вычисленную с * помощью функции overlap(s1, s2) */ private static String merge(String s1, String s2, int len)

Один пример (худший случай):
● Ввод: S =
● Вывод жадного алгоритма: «ab k cb k+1 » с длиной 4+4k
● Вывод оптимального алгоритма: «ab k+1 c» с длиной 4+2k

Коэффициент приближения исходя из худшего случая

4-приближённый алгоритм Блюма-Янга-Ли-Тромпа-Яннакакиса

Вообще говоря, у этого алгоритма нет названия и так, как я, его никто не называет. Называется он просто 4-приближённый алгоритм конструирования кратчайшей надстроки. Но так как его придумали Блюм, Янг, Ли, Тромп и Яннакакис, почему бы не дать такой заголовок?

Для наглядности, во время разбора алгоритма я буду приводить пример построения надстроки для набора S = 0: “cde”, S₁: “abc”, S₂: “eab”, S₃: “fgh”, S₄: “ghf”, S₅: “hed”>.

Основной идеей алгоритма является нахождение покрытия циклами минимальной полной длины для полного направленного взвешенного графа, вершинами которого являются строки заданного набора, а вес ребра из S_i в S_j равен overlap(S_i, S_j) для всех i, j.

Граф для нашего примера (вершины для видимости подписаны i вместо S_i):

В своей реализации я буду представлять этот граф как матрицу смежности, которая будет формироваться банальным образом, показанном в следующем листинге (в п.16.17 [1] Д. Гасфилд утверждает, что матрицу можно формировать эффективнее, но способ формирования этой матрицы не влияет на рассмотрение данного алгоритма).

 int n = strings.size(); // Вычисление матрицы overlap'ов для всех // упорядоченных пар (Si, Sj). int[][] overlaps = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) overlaps[i][j] = overlap(strings.get(i), strings.get(j));

Для нашего примера матрица смежности будет выглядеть так:

После того, как матрица смежности построена, встаёт необходимость найти покрытие циклами минимальной полной длины. Такое покрытие можно найти, сводя эту задачу к “задаче о назначениях”. Итак, задачей стало найти полное назначение максимального веса (как оказалось, этот шаг алгоритма занимает доминантное время). Быстрее и проще ([1] п.16.19.13) это назначение можно найти жадным методом.

Жадное назначение ([1] п.16.19.13)

Исходные данные: матрица A размером k × k.
Результат: полное назначение M.

Положить M = Ø и объявить все клетки A доступными.
while в A есть доступные клетки do begin
1. Среди доступных клеток A выбрать клетку (i, j) наибольшего веса.
2. Поместить клетку (i, j) в M и сделать клетки в строчке i и столбце j недоступными.
3. end;
Представить M в коде можно в виде массива (int[] M = new int[k]) и первую часть инструкции 2.2 трактовать как M[i] = j; так как в полном назначении каждое число от 0 до k встречается ровно один раз как индекс строки и ровно один раз как индекс столбца.

Пример реализации вычисления полного назначения представлен в следующем листинге.
```
 /* * Функция, вычисляющая полное назначение максимального * веса жажным методом. Время - O(k*k*log(k)) */ private static int[] assignment(int[][] a) < int n = a.length; boolean[][] notallow = new boolean[n][n]; int[] m = new int[n]; while (true) < int max = -1, maxi = -1, maxj = -1; for (int i = 0; i < n; i++) < for (int j = 0; j < n; j++) < if (notallow[i][j]) continue; if (a[i][j] >max) < max = a[i][j]; maxi = i; maxj = j; >> > if (max == -1) break; m[maxi] = maxj; for (int i = 0; i < n; i++) < notallow[maxi][i] = true; notallow[i][maxj] = true; >> return m; > 
```
Пошаговое вычисление полного назначения максимального веса жадным методом для нашего примера:

Теперь, когда вычислено полное назначение максимального веса, необходимо вычислить покрытие циклами минимальной полной длины. Для этого нужно:

взяв за начало любой (логично – нулевой) индекс полного назначения, положить его в цикл, пометить использованным и посмотреть, равняется ли его значение индексу начала цикла? Если да – закончить цикл, положить его в покрытие циклами и начать новый цикл, взяв за начало первый непомеченный элемент. Если нет – взять это значение за индекс и повторить процедуру, пока все элементы не станут помечены.

Представление покрытия циклами в памяти можно организовать как список списков индексов строк.

Листинг алгоритма (assign – полное назначение):
```
 // Нахождение покрытия циклами минимальной полной длины // для полного назначения assign ArrayList> cycles = new ArrayList>(); ArrayList cycle = new ArrayList(); boolean[] mark = new boolean[assign.length]; for (int i = 0; i < assign.length; i++) < if (mark[i]) continue; cycle.add(i); mark[i] = true; if (assign[i] == cycle.get(0)) < cycles.add(cycle); cycle = new ArrayList(); i = 0; > else < i = assign[i] - 1; >> 
```
Для нашего примера нахождение покрытия циклами будет выглядеть следующим образом:

Получившееся покрытие циклами можно отобразить на изначальном графе, оставив на нём только те рёбра, которые попали в покрытие.

Сборка. Теперь, когда все циклы в покрытии вычислены, можно приступать к сборке, непосредственно, надстроки.

Для этого понадобится функция prefix, которая принимает строки S₁ и S₂ и возвращает строку S₁, обрезанную справа на overlap(S₁, S₂) символов. Но так как все overlap’ы были нами давно посчитаны, то функцию можно написать так, чтобы она принимала только одну строку и количество символов, на которое её нужно укоротить.
```
 /* * Функция возвращает строку s1, обрезанную справа * на ov символов */ private static String prefix(String s1, int ov)
```
Проблема состоит в том, что, так как циклы в покрытии – это циклы — значит, мы можем их циклически крутить и непонятно, с какой строки начать конструирование надстроки X_Ci. Ответ оказывается прост – нужно сдвинуть цикл так, чтобы минимизировать overlap последней и первой строки.

Рассмотрим первый цикл циклического покрытия из примера.

Если не минимизировать overlap последней и первой строки, а взять C₀ = , то надстрокой будет X_C0 = abc ++ cde ++ eab = abcdeab, очевидно, не самая короткая из возможных. Минимальный overlap в этом цикле – 1, значит, нам подойдёт любая из последовательностей (cde ++ eab ++ abc = cdeabc) или (eab ++ abc ++ cde = eabcde).
Далее приведён код, который циклически сдвигает каждый цикл в покрытии так, чтобы минимизировать overlap’ы первых и последних строк каждого цикла, и конструирует надстроки для каждого цикла.
```
 // Циклический сдвиг каждого цикла в покрытии такой, чтобы // минимизировать overlap первой и последней строки в цикле // и конструирование надстроки для каждого цикла. ArrayList superstrings = new ArrayList(); for (ArrayList c : cycles) < String str = ""; ArrayListovs = new ArrayList(); for (int i = 0; i < c.size() - 1; i++) ovs.add(overlaps[c.get(i)][c.get(i+1)]); int min = overlaps[c.get(c.size()-1)][c.get(0)]; int shift = 0; for (int i = 0; i < ovs.size(); i++) if (ovs.get(i) < min) < min = ovs.get(i); shift = i + 1; >Collections.rotate(c, -shift); for (int i = 0; i
```
Теперь у нас есть кратчайшие надстроки для каждого цикла в покрытии. Рассматриваемый алгоритм с множителем 4 предполагает простую конкатенацию этих строк.
```
 // Конкатенация всех надстрок из superstrings StringBuilder superstring = new StringBuilder(); for (String str : superstrings) superstring.append(str); return superstring.toString(); 
```
Исходные коды и тестирование

Исходные коды жадного (Greedy.java) и Блюма-Янга-Ли-Тромпа-Яннакакиса (Assign.java) алгоритмов доступны в git-репозитории по ссылке bitbucket.org/andkorsh/scss/src. Также там есть исполняемый класс Main.java, который при запуске запрашивает количество запусков для замера скорости алгоритмов и путь к входному файлу. Также класс Main умеет генерировать входные данные сам, для этого вместо имени файла нужно ввести «random», после чего будет запрошено количество строк, максимальная длина строки, фиксированная длина или нет и количество символов в алфавите. Отчёт запишется в файл output.txt.

Исходные коды гарантированно компилируются javac, начиная с версии “1.6.0_05”.

Тестирование выполняется с помощью функции test класса Main.
```
 private static int test(ArrayList substrings, String superstring)
```
Использованная литература

[1]: Дэн Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект, БХВ-Петербург, 2003г. – 656 с.: ISBN 5-7940-0103-8, 5-94157-321-9, 0-521-58519-8.
www.ozon.ru/context/detail/id/1393109

[2]: Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE, 1997г. – 534 с.: ISBN-10: 0521585198, ISBN-13: 978-0521585194.
www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198

[3]: Shunji Li, Wenzheng Chi. Lecture #3: Shortest Common Superstring – CS 352 (Advanced Algorithms), Spring 2011.
cs.carleton.edu/faculty/dlibenno/old/cs352-spring11/L03-shortest-superstring.pdf

Java String. Вопросы к собеседованию и ответы на них, ч.2

К сожалению статья не поместилась одним фрагментом, пришлось разбить её на две части. Начало смотрите тут

12. Напишите функцию для нахождения самого длинного палиндрома в данной строке

Строка может содержать в себе строки-палиндромы, и нахождение самого длинного палиндрома – это вопрос программирования. Ключевым моментом здесь является то, что из середины любого палиндрома, если мы пойдем направо и налево на 1 символ, это всегда будет одинаковый символ. К примеру, 12321, середина тут 3, и если мы продолжим движение с текущей позиции в обе стороны, мы получим 2, а затем 1. Мы используем подобную логику в нашей Java программе для нахождения самого длинного палиндрома. Однако если длина палиндрома четная, длина середины тоже четная, так что мы должны убедиться, что в нашей программе это так же предусмотрено, к примеру, 12333321, тут середина 33, и если мы продолжим движение в обе стороны, мы получим 3, 2 и 1. В нашей программе мы проходим по полученной строке с серединой на первом месте и проверяем левый и правый символ. Так же мы имеем две глобальные переменные для хранения начальной позиции палиндрома. Нам также необходимо проверить наличие уже найденного более длинного палиндрома, так как мы можем найти несколько палиндромов в данной строке. Ниже приведен пример программы, которая отлично работает во всех случаях. Мы можем усовершенствовать приведенный код, переместив цикл while в отдельный метод, но я оставил эту часть для вас . Пожалуйста, дайте мне знать, если у вас есть более удачная реализация, или программа не срабатывает в каком-то случае.
```
 package com.journaldev.util; public class LongestPalindromeFinder < public static void main(String[] args) < System.out.println(longestPalindromeString("1234")); System.out.println(longestPalindromeString("12321")); System.out.println(longestPalindromeString("9912321456")); System.out.println(longestPalindromeString("9912333321456")); System.out.println(longestPalindromeString("12145445499")); >public static String longestPalindromeString(String in) < char[] input = in.toCharArray(); int longestPalindromeStart = 0; int longestPalindromeEnd = 0; for (int mid = 0; mid < input.length; mid++) < // для случая нечетного палиндрома как 12321, 3 будет серединой int left = mid-1; int right = mid+1; // нам необходимо двигаться влево и вправо на 1 позицию до конца while (left >= 0 && right < input.length) < // ниже проверка, является ли это палиндромом if (input[left] == input[right]) < // обновление глобальных позиций, только если палиндром длиннее имеющегося if (right - left >longestPalindromeEnd - longestPalindromeStart) < longestPalindromeStart = left; longestPalindromeEnd = right; >> left--; right++; > // для четного палиндрома у нас должна быть подобная логика с размером середины 2 // для этого мы начнем на одну позицию правее left = mid-1; right = mid + 2;// к примеру, для 12333321 мы выбрали 33 в качестве середины while (left >= 0 && right < input.length) < if (input[left] == input[right]) < if (right - left >longestPalindromeEnd - longestPalindromeStart) < longestPalindromeStart = left; longestPalindromeEnd = right; >> left--; right++; > > // теперь у нас есть позиции для самого длинного палиндрома return in.substring(longestPalindromeStart, longestPalindromeEnd + 1); > > 
```
Программа выведет следующее:
```
 1 12321 12321 12333321 454454 
```
13. Какие различия между String, StringBuffer и StringBuilder

Строка является неизменной и финализированной в Java, поэтому все наши манипуляции со строкой всегда будут создавать новую строку. Манипуляции со строками ресурсоемкие, поэтому Java обеспечивает два полезных класса для манипуляций со строками – StringBuffer и StringBuilder . StringBuffer и StringBuilder являются изменяемыми классами. Операции с StringBuffer потокобезопасны и синхронизированы, а методы StringBuilder не потокобезопасны. Поэтому когда несколько нитей работают с одной строкой, мы должны использовать StringBuffer , но в однопоточном окужении мы должны использовать StringBuilder . StringBuilder более производительный, чем StringBuffer , поскольку не обременен синронизацией.

14. Почему строка неизменная и финализированная в Java
1. Строковый пул возможен только потому, что строка неизменна в Java, таким образом виртуальная машина сохраняет много места в памяти (heap space), поскольку разные строковые переменные указывают на одну переменную в пуле. Если бы строка не была неизмененяемой, тогда бы интернирование строк не было бы возможным, потому что если какая-либо переменная изменит значение, это отразится также и на остальных переменных, ссылающихся на эту строку.
2. Если строка будет изменяемой, тогда это станет серьезной угрозой безопасности приложения. Например, имя пользователя базы данных и пароль передаются строкой для получения соединения с базой данных и в программировании сокетов реквизиты хоста и порта передаются строкой. Так как строка неизменяемая, её значение не может быть изменено, в противном случае любой хакер может изменить значение ссылки и вызвать проблемы в безопасности приложения.
3. Так как строка неизменная, она безопасна для много поточности и один экземпляр строки может быть совместно использован различными нитями. Это позволяет избежать синхронизации для потокобезопасности, строки полностью потокобезопасны.
4. Строки используются в Java classloader и неизменность обеспечивает правильность загрузки класса при помощи Classloader . К примеру, задумайтесь об экземпляре класса, когда вы пытаетесь загрузить java.sql.Connection класс, но значение ссылки изменено на myhacked.Connection класс, который может осуществить нежелательные вещи с вашей базой данных.
5. Поскольку строка неизменная, её hashcode кэшируется в момент создания и нет необходимости рассчитывать его снова. Это делает строку отличным кандидатом для ключа в Map и его обработка будет быстрее, чем других ключей HashMap . Это причина, почему строка наиболее часто используемый объект, используемый в качестве ключа HashMap .
15. Как разделить строку на части?

Мы можем использовать метод split(String regex) для разделения строки на массив строк, используя в качестве разделителя регулярное выражение.
```
 import java.util.Arrays; public class JavaSplitString < public static void main(String[] args) < String line = "I am a java developer"; String[] words = line.split(" "); String[] twoWords = line.split(" ", 2); System.out.println("String split with delimiter: "+Arrays.toString(words)); System.out.println("String split into two: "+Arrays.toString(twoWords)); //split string delimited with special characters String wordsWithNumbers = "I|am|a|java|developer"; String[] numbers = wordsWithNumbers.split("\\|"); System.out.println("String split with special character: "+Arrays.toString(numbers)); >> 
```
Метод split(String regex, int numOfStrings) является перегруженным методом для разделения строки на заданное количество строк. Мы можем использовать обратную черту для использования специальных символов регулярных выражений в качестве обычных символов. Программа выведет следующее:
```
 String split with delimiter: [I, am, a, java, developer] String split into two: [I, am a java developer] String split with special character: [I, am, a, java, developer] 
```
16. Почему массив строк предпочтительнее строки для хранения пароля?

Строка неизменяемая в Java и хранится в пуле строк. С тех пор, как она была создана, она остается в пуле, пока не будет удалена сборщиком мусора, поэтому, когда мы думаем, что закончили работу с паролем, он остается доступным в памяти некоторое время, и нет способа избежать этого. Это риск безопасности, поскольку кто-либо, имеющий доступ к дампу памяти сможет найти пароль в виде чистого текста. Если мы используем массив символов для хранения пароля, мы можем очистить его после того, как закончим с ним работать. Таким образом, мы можем контролировать, как долго он находится в памяти, что позволяет избежать риска безопасности, свойственного строке.

17. Как вы проверите две строки на подобность в Java?

Есть два способа проверить, являются ли две строки эквивалентными – используя оператор “ == ”, или используя метод equals . Когда мы используем оператор “ == ”, он проверяет значение строки, как ссылки, но в программировании большую часть времени мы проверяем эквивалентность строки только для значения. Поэтому мы должны использовать метод equals для проверки двух строк на эквивалентность. Еще есть метод equalsIgnoreCase , который мы можем использовать для игнорирования регистра.
```
 String s1 = "abc"; String s2 = "abc"; String s3= new String("abc"); System.out.println("s1 == s2 ? "+(s1==s2)); //true System.out.println("s1 == s3 ? "+(s1==s3)); //false System.out.println("s1 equals s3 ? "+(s1.equals(s3))); //true 
```
18. Что такое пул строк?

Как подсказывает название, пул строк – это набор строк, который хранится в памяти Java heap. Мы знаем, что String это специальный класс в Java, и мы можем создавать объекты этого класса, используя оператор new точно так же, как и создавать объекты, предоставляя значение строки в двойных кавычках. Диаграмма ниже объясняет, как пул строк размещается в памяти Java heap и что происходит, когда мы используем различные способы создания строк. Пул строк возможен исключительно благодаря неизменяемости строк в Java и реализации идеи интернирования строк. Пул строк также является примером паттерна Приспособленец (Flyweight). Пул строк помогает экономить большой объем памяти, но с другой стороны создание строки занимает больше времени. Когда мы используем двойные кавычки для создания строки, сначала ищется строка в пуле с таким же значением, если находится, то просто возвращается ссылка, иначе создается новая строка в пуле, а затем возвращается ссылка. Тем не менее, когда мы используем оператор new, мы принуждаем класс String создать новый объект строки, а затем мы можем использовать метод intern() для того, чтобы поместить строку в пул, или получить из пула ссылку на другой объект String с таким же значением. Ниже приведен пример, показывающий работу пула строк.
```
 public class StringPool < public static void main(String[] args) < String s1 = "Cat"; String s2 = "Cat"; String s3 = new String("Cat"); System.out.println("s1 == s2 :"+(s1==s2)); System.out.println("s1 == s3 :"+(s1==s3)); >> 
```
Программа выведет следующее:
```
 s1 == s2 :true s1 == s3 :false 
```
19. Что делает метод intern()?

Когда метод intern() вызван, если пул строк уже содержит строку, эквивалентную к нашему объекту, что подтверждается методом equals(Object) , тогда возвращается ссылка на строку из пула. В противном случае объект строки добавляется в пул и ссылка на этот объект возвращается. Этот метод всегда возвращает строку, которая имеет то же значение, что что и текущая строка, но гарантирует что это будет строка из пула уникальных строк. Ниже приведен пример работы метода intern() :
```
 public class StringPool < public static void main(String[] args) < String a = "string a"; String b = new String("string a"); String c = b.intern(); System.out.println(a == b); System.out.println(b == c); System.out.println(a == c); >> Программа выведет следующее: false false true 
```
20. Являются ли строки потокобезопасными в Java?

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

21. Почему строка является популярным ключем в HashMap в Java?

Поскольку строки неизменны, их хэшкод кэшируется в момент создания, и не требует повторного пересчета. Это делает строки отличным кандидатом для ключа в Map и они обрабатываются быстрее, чем другие объекты-ключи HashMap . Вот почему строки преимущественно используются в качестве ключей HashMap . Надеюсь, что вопросы, перечисленные в этой статье помогут вам на собеседованиях, пожалуйста, дайте мне знать, если я что-то пропустил. Ссылка на оригинальную статью Автор: Pankaj Kumar

Различаются ли строки не более чем на один символ?

Есть две строки как проверить, что из одной можно сделать другую при помощи вставки, удаления или замены не более чем одного символа?

Отслеживать
задан 1 янв 2016 в 14:06
123k 24 24 золотых знака 126 126 серебряных знаков 303 303 бронзовых знака
Ваш вопрос участвует в конкурсе: Новогодний алгоритм 2016
3 янв 2016 в 11:50

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

Минимальное количество операций вставки, удаления и замены символа, необходимое для преобразования одной строки в другую, называется расстоянием Левенштейна. В общем случае оно вычисляется за O(n*m) , где n и m - длины строк.

Однако, в данном случае требуется не вычислить количество действий, а проверить, возможно ли сделать преобразование за 0 (строки изначально одинаковые) или 1 действие.

Рассмотрим две строки. Выделим наидлиннейший одинаковый префикс и наидлиннейший одинаковый суффикс (допускается, что один или оба найденных куска могут быть пустыми). Очевидно, что в этих кусках нам ничего менять не требуется. Центральной частью строки назовём участок между префиксом и суффиксом.

Рассмотрим несколько возможных ситуаций:
- (1) Префикс и суффикс совпадают со всей строкой. Строки были изначально одинаковы.
- Конкатенация префикс и суффикса даёт одну из строк. В таком случае для того, чтобы преобразование было возможно, необходимо и достаточно, чтобы центральная часть другой строки состояла из одного символа. Понадобится операция вставки или удаления.
- Центральная часть обеих строк состоит из одного символа. Нужна операция замены.
- Центральная часть хотя бы одной из строк состоит из нескольких символов. Преобразование невозможно.
- (2) Т. о. для различных строк необходимо и достаточно, чтобы центральная часть каждой из строк была не длиннее одного символа.
Несколько преобразуем этот алгоритм:
- Найдём индекс S , указывающий на следующий символ за одинаковым префиксом (возможно, длина строки плюс 1).
- Найдём индексы E1 и E2 , указывающие на символ, предшествующий одинаковому суффиксу в первой и второй строках соответственно (возможно, -1). Они могут различаться, т. к. длина строк может быть разной.
- В случае 1 получим S=Length+1, E1=-1, E2=-1 .
- Центральная часть нулевой длины означает, что указатель конца будет стоять раньше указателя начала на 1 символ.
  Центральная часть из одного символа будет представлена равными указателями конца и начала.
  Во всех остальных случаях указатель конца будет больше.
- Т. о. для (2) условие превратится в такое:
  Для обеих строк указатель конца не превосходит указателя начала.
- Заметим, что для одинаковых строк это условие так же выполняется.
- Если язык позволяет, то можно (в качестве дополнительной оптимизации) сначала проверить, что длины строк отличаются не более чем на 1.
А теперь в коде:
```
Public Function AreSimilar(ByVal Str1 As String, ByVal Str2 As String) As Boolean If Math.Abs(Str1.Length - Str2.Length) > 1 Then Return False Dim S As Integer = 0 Dim E1 As Integer = Str1.Length - 1, E2 As Integer = Str2.Length - 1 Dim MinLength As Integer = Math.Min(E1 + 1, E2 + 1) Do While S < MinLength AndAlso Str1(S) = Str2(S) S += 1 Loop Do While Not E1 AndAlso Not E2 AndAlso Str1(E1) = Str2(E2) E1 -= 1 E2 -= 1 Loop Return E1  
```
Асимптотика линейная. В худшем случае (при одинаковых строках) делается по два полных прохода по каждой из строк. Отслеживать ответ дан 1 янв 2016 в 14:06 123k 24 24 золотых знака 126 126 серебряных знаков 303 303 бронзовых знака В языках, наследниках C длина строки определяется только по наличию 0 в конце, поэтому получение длины строки = полному проходу по ней 1 янв 2016 в 14:40 @Mike 0. Только с Си и Си++. В других сиподобных - нет. 1. Даже если для длины нужен проход по строке, это не отменяет линейности. 2. Плюс, мы можем проверить в первом цикле str1[s] , если конец не достигнут, то узнать длину как s+strlen(str+s) , получив за один проход и длину префикса, и длину строки. Таким образом сохраним не более двух проходов. 1 янв 2016 в 14:46 @Mike, в таких языках длина вполне может передаваться параметром в функцию 1 янв 2016 в 14:51 Не видать мне плюсиков без кода на си, да? 1 янв 2016 в 15:01 @YuriNegometyanov: dotnetfiddle.net/jhf63h 3 янв 2016 в 11:51 Алгоритм для случая, когда длины строк заранее не известны и в общем случае вообще не доступны, т.е. это потоки байт или файлы целиком не умещающиеся в памяти. int teststr(char *s1,char *s2) < int k0=1,k1=1,k2=1; while(*s1==*s2 && *s1) // Ищем первое несовпадение char o1,o2; if(!*s1 && !*s2) return 1; // Строки равны do < o1=*s1++; o2=*s2++; k0=k0 && c1==c2; k1=k1 && c1==o2; k2=k2 && c2==o1; if(!(k0 | k1 | k2)) return 0; // Обнаружена ошибка (строки не преобразуемы) >while(o1 && o2); if( (!o1 && *s2) || (!o2 && *s1) ) return 0; // Расхождение длин строк более чем на 1 return 2; // Строки преобразуемы за одно действие > Работает за один прямой проход строки до конца (если строки равны) или до первой обнаруженной ошибки. Т.е. максимальная сложность O(n). Сначала идет сканирование строк до первого несовпадения. После этого начинается цикл идущий от точки несовпадения. Он сравнивает текущие символы двух строк, они равны в случае если предыдущее расхождение было заменой символа. А так же текущий символ одной строки с предыдущим символом другой строки, они равны в случаях если один символ был вставлен или удален и следовательно произошел сдвиг одной из строк. Одно из этих равенств должно сохранятся от точки когда было встречено первое расхождение и до конца строк. Для любителей UTF-8 привожу полный код, нормально разбирающий данную кодировку с символами разной длины. Замечу, что он поймет любые символы, включая китайские иероглифы и т.п. Если нужна кодировка с символами фиксированной длины, большей чем байт, т.е. например UTF-16, то это решается проще, заменой char на short в предыдущем коде. #include unsigned int utf32(char **s) < unsigned char b=(unsigned char)**s; unsigned int code=0; int n=-1; if(b) (*s)++; if(! (b & 0x80) ) return b; bcode|= b int teststr(char *s1,char *s2) < int k0=1,k1=1,k2=1; unsigned int c1,c2,o1,o2; do while(c1==c2 && c1); if(!c1 && !c2) return 1; do < o1=c1; o2=c2; c1=utf32(&s1); c2=utf32(&s2); k0=k0 && c1==c2; k1=k1 && c1==o2; k2=k2 && c2==o1; if(!(k0 | k1 | k2)) return 0; >while(o1 && o2); if( (!o1 && c2) || (!o2 && c1) ) return 0; return 1; > int main() Похожие публикации: Как поменять смик на ргб в иллюстраторе Как разбить строку на символы с Как сделать принтскрин на клавиатуре apple в windows Как увеличить шрифт в убунту

Length s2 n2 1 зачем нужно

Строки

Методы строк

Методы split() и join()

Методы find() и replace()

Метод format()

Практическая работа

Shortest Common Superstring Problem

Жадный алгоритм

4-приближённый алгоритм Блюма-Янга-Ли-Тромпа-Яннакакиса

Исходные коды и тестирование

Использованная литература

Java String. Вопросы к собеседованию и ответы на них, ч.2

12. Напишите функцию для нахождения самого длинного палиндрома в данной строке

13. Какие различия между String, StringBuffer и StringBuilder

14. Почему строка неизменная и финализированная в Java

15. Как разделить строку на части?

16. Почему массив строк предпочтительнее строки для хранения пароля?

17. Как вы проверите две строки на подобность в Java?

18. Что такое пул строк?

19. Что делает метод intern()?

20. Являются ли строки потокобезопасными в Java?

21. Почему строка является популярным ключем в HashMap в Java?

Различаются ли строки не более чем на один символ?

3 ответа 3

Добавить комментарий Отменить ответ