Изучаем функции php для работы со строками. часть 1

Обрабатываем строку в Python

Представим, что ожидается ввод числа с клавиатуры. Перед преобразованием введенной нами строки в число можно легко проверить, введено ли действительно число. Если это так, выполнится операция преобразования. Для обработки строки используем такой метод в Python, как isnumeric():


string = input("Введите какое-нибудь число: ")
if string.isnumeric():
    number = int(string)
    print(number)

Следующий пример позволяет удалять пробелы в конце и начале строки:

string = "   привет мир!  "
string = string.strip()
print(string)           # привет мир!

Так можно дополнить строку пробелами и выполнить выравнивание:

print("iPhone 7:", "52000".rjust(10))
print("Huawei P10:", "36000".rjust(10))

В консоли Python будет выведено следующее:

iPhone 7      52000
Huawei P10      36000

Особенности функций для работы со строками

Языки программирования могут включать специальные функции для работы со строками, избавляя тем самым программиста от необходимости писать собственные функции обработки строк. Например, часто требуется определить длину строки, и поэтому в языках предусмотрена функция, измеряющая ее длину.

В языке программирования C функции для работы со строками объявляются в заголовочном файле string.h, который надо не забывать подключать к своему исходному коду. Существует около двадцати функций для работы со строками. Среди них есть те, которые осуществляют поиск символов в строке, функции сравнения, копирования строк, а также более специфические. Перечень и описание большинства существующих на данный момент в языке C функций можно найти в приложении книги Б. Кернигана, Д. Ритчи «Язык программирования C. Второе издание».

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

Например, функция  имеет такое объявление: . Она копирует строку, на которую указывает второй параметр, в строку, на которую указывает первый параметр. Таким образом первый параметр изменяется. Кроме того, функция возвращает указатель на первый символ строки:

	char s110, s210;
	char *s3;
	s3 = s2;
 
	gets(s1);
	s3 = strcpy(s2,s1);
	puts(s2);
	puts(s3);
	printf("%p, %p\n", s2, s3);

Здесь s2 и s3 указывают на один и тот же символ ( выводит одинаковые адреса). Однако то, что возвращает , нельзя присвоить массиву. Результат работы этой функции обычно ничему не присваивают; бывает достаточно того, что она просто изменяет одну из переданных по указателю строк.

Другое дело, такие функции как  или , которые не изменяют параметры, а вызываются ради результата. Функция  сравнивает две строки-аргумента по буквам (лексикографически) и возвращает 0, -1 или 1. Например, вызов  вернет 1, т.к. код буквы ‘y’ больше буквы ‘d’. Вызов  вернет -1, т.к. первый аргумент лексикографически меньше второго.

Эффективный алгоритм поиска[править]

Z-блоком назовем подстроку с началом в позиции и длиной . Для работы алгоритма заведём две переменные: и — начало и конец Z-блока строки с максимальной позицией конца (среди всех таких Z-блоков, если их несколько, выбирается наибольший). Изначально и . Пусть нам известны значения Z-функции от до . Найдём . Рассмотрим два случая.

  1. :Просто пробегаемся по строке и сравниваем символы на позициях и .Пусть первая позиция в строке для которой не выполняется равенство , тогда это и Z-функция для позиции . Тогда . В данном случае будет определено корректное значение в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.
  2. :Сравним и . Если меньше, то надо просто наивно пробежаться по строке начиная с позиции и вычислить значение . Корректность в таком случае также гарантирована.Иначе мы уже знаем верное значение , так как оно равно значению .

Время работыправить

Этот алгоритм работает за , так как каждая позиция пробегается не более двух раз: при попадании в диапазон от до и при высчитывании Z-функции простым циклом.

Псевдокодправить

 int[] zFunction(s : string):
   int[] zf = int
   int left = 0, right = 0
   for i = 1 to n − 1
     zf = max(0, min(right − i, zf))
     while i + zf < n and s] == s]
       zf++
     if i + zf > right
       left = i
       right = i + zf
   return zf

Решение[править]

Алгоритмправить

Алгоритм начинается с подсчета и , а также с подсчета , для ускорения ответов на запрос.

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

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

Псевдокодправить

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

vector<int> rabinKarp (s : string, w : string):
   vector<int> answer
   int n = s.length
   int m = w.length
   int hashS = hash(s)
   int hashW = hash(w)
   for i = 0 to n - m
        if hashS == hashW
             answer.add(i)
        hashS = (p * hashS - p * hash(s) + hash(s)) mod r 
   return answer

Новый хеш был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что — пустой символ.

Время работыправить

Изначальный подсчёт хешей выполняется за .

Каждая итерация выполняется за , В цикле всего итераций.

Итоговое время работы алгоритма .

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

Функция 3

Вдруг нам нужно будет выделить в строке несколько символов подряд ,например, со второго по десятый символ в строке. В этом нам поможет php функция substr().

PHP

<?php $string = ‘Особенности национальной охоты’; $string2 = substr($string,0,11); //выбираем из строки символы с 0 позиции, кол-во выбранных символов = 11 (длинна слова «Особенности») echo $string2.'<br>’; ?>

1 2 3 4 5

<?php

$string=’Особенности национальной охоты’;

$string2=substr($string,,11);//выбираем из строки символы с 0 позиции, кол-во выбранных символов = 11 (длинна слова «Особенности»)

echo$string2.'<br>’;

?>

Замечание: функция неадекватно работает с кодировкой файла в UTF8.

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

Пример: выберем слово «охоты»:

PHP

<?php $string = ‘Особенности национальной охоты’; $string2 = substr($string,-5); //выбираем из строки символы с 0 позиции, если не указать третий параметр (сколько символов выберать), то выбор пойдет до конца строки echo $string2.'<br>’; // выведет на экран «охоты» ?>

1 2 3 4 5

<?php

$string=’Особенности национальной охоты’;

$string2=substr($string,-5);//выбираем из строки символы с 0 позиции, если не указать третий параметр (сколько символов выберать), то выбор пойдет до конца строки

echo$string2.'<br>’;// выведет на экран «охоты»

?>

Обсуждение¶

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

В первой попытке написать эти шаблоны я столкнулся с неприятным эффектом, о котором вы должны помнить, когда работаете с рекурсивными шаблонами. Напомню, что выражение всегда возвращает ! Поэтому при рекурсивном вызове и я проверяю, что значение не пусто. Без такой проверки мы попали бы в бесконечный цикл поиска пустой подстроки, а если реализация не поддерживает хвостовую рекурсию, то произошло бы переполнение стека.

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

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

Для чего нужно так много алгоритмов?

На сегодняшний день существует огромное разнообразие алгоритмов поиска подстроки. Программисту приходится выбирать подходящий в зависимости от таких факторов.

  1. Нужна ли вообще оптимизация, или хватает примитивного алгоритма? Как правило, именно его реализуют стандартные библиотеки языков программирования.
  2. «Враждебность» пользователя. Другими словами: будет ли пользователь намеренно задавать данные, на которых алгоритм будет медленно работать? Существуют очень простые алгоритмы, оценка которых O(|haystack|·|needle|) в худшем случае, но на «обычных» данных количество сравнений намного меньше |haystack|. Только в 1990-е годы были созданы алгоритмы, дающие сложность O(|haystack|) в худшем случае и меньше |haystack| в среднем.
  3. Грамматика языка может быть недружественной к тем или иным эвристикам, которые ускоряют поиск «в среднем».
  4. Архитектура процессора. Некоторые процессоры имеют автоинкрементные или SIMD-операции, которые позволяют быстро сравнить два участка ОЗУ (например, на x86). На таких процессорах заманчиво применить алгоритм, который просто бы сравнивал needle с haystack — разумеется, не во всех позициях.
  5. Размер алфавита. Многие алгоритмы (особенно основанные на сравнении с конца) имеют эвристики, связанные с несовпавшим символом. На больших алфавитах таблица символов будет занимать много памяти, на малых — соответствующая эвристика будет неэффективной.
  6. Возможность проиндексировать haystack. Если таковая есть, поиск серьёзно ускорится.
  7. Требуется ли одновременный поиск нескольких строк? Приблизительный поиск? Побочные свойства некоторых алгоритмов (Ахо-Корасик, двоичного алгоритма) позволяют такое.

Как правило, в текстовом редакторе достаточно взять самый простой эвристический алгоритм наподобие Бойера — Мура — Хорспула — даже очень медленный ПК справится с поиском за доли секунды. Если же объём текста измеряется гигабайтами, либо поиск запущен на сервере, который обрабатывает множество запросов — приходится выбирать наиболее удачный алгоритм из доступных. Например, программы определения плагиата осуществляют онлайн-проверку, используя алгоритмы поиска подстроки среди большого количества документов, хранящихся в собственной базе.

Поиск подстроки в строке – реализация

Объяснять материал мы будем на примере языка программирования Java, а в конце статьи приведем реализацию учебного примера на языке C#.

Объявим строку (proverb) и две подстроки (substring1, substring2):


Java

String proverb = «Без труда не вытащишь рыбку из пруда»;

String substring1 = «да»;

String substring2 = «нет»;

1 2 3 4 5

Stringproverb=»Без труда не вытащишь рыбку из пруда»;

Stringsubstring1=»да»;

Stringsubstring2=»нет»;

Для того, чтобы выполнить поиск подстроки в строке в Java используется метод indexOf. Он возвращает индекс ПЕРВОГО вхождения подстроки в сроку. Если подстрока в строке не обнаружена, то будет возвращено число -1.

Java

proverb.indexOf(substring1); //будет возвращено 7

proverb.indexOf(substring2); //будет возвращено -1

1 2 3

proverb.indexOf(substring1);//будет возвращено 7

proverb.indexOf(substring2);//будет возвращено -1

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

Java

proverb.indexOf(substring1, 10); //будет возвращено 34

1 proverb.indexOf(substring1,10);//будет возвращено 34

Также есть метод, осуществляющий поиск ПОСЛЕДНЕГО вхождения подстроки в строку. Он называется lastIndexOf. Номер начального символа поиска также можно указать.

Java

proverb.lastIndexOf(substring1); //будет возвращено 34

1 proverb.lastIndexOf(substring1);//будет возвращено 34

Приводим полный листинг написанного кода на Java, а также демонстрацию работы консольной программы. Ниже, Вы можете скачать исходник, написанный в среде разработки NetBeans IDE.

Java

package findsubstring;

public class FindSubstring {

public static void main(String[] args) { String proverb = «Без труда не вытащишь рыбку из пруда»;

String substring1 = «да»;

String substring2 = «нет»; System.out.println(proverb.indexOf(substring1));

System.out.println(proverb.indexOf(substring2));

System.out.println(proverb.indexOf(substring1, 10));

System.out.println(proverb.lastIndexOf(substring1)); } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

packagefindsubstring;

publicclassFindSubstring{

publicstaticvoidmain(Stringargs){

Stringproverb=»Без труда не вытащишь рыбку из пруда»;

Stringsubstring1=»да»;

Stringsubstring2=»нет»;

System.out.println(proverb.indexOf(substring1));


System.out.println(proverb.indexOf(substring2));

System.out.println(proverb.indexOf(substring1,10));

System.out.println(proverb.lastIndexOf(substring1));

}

}

Скачать исходник (Java)

Теперь поиск подстроки в строке на языке C#. Код очень похож на то, что было выше, ибо методы называются одинаково и имеют идентичную сигнатуру.

Решим аналогичную задачу. Приводим листинг написанной программы на C#. Исходник можно скачать ниже (написан в Visual Studio).

C#

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace FindSubstring { class Program { static void Main(string[] args) { string proverb = «Без труда не вытащишь рыбку из пруда»;

string substring1 = «да»;

string substring2 = «нет»;

Console.WriteLine(proverb.IndexOf(substring1));

Console.WriteLine(proverb.IndexOf(substring2));

Console.WriteLine(proverb.IndexOf(substring1, 10));

Console.WriteLine(proverb.LastIndexOf(substring1)); } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespaceFindSubstring

{

classProgram

{

staticvoidMain(stringargs)

{

stringproverb=»Без труда не вытащишь рыбку из пруда»;

stringsubstring1=»да»;

stringsubstring2=»нет»;

Console.WriteLine(proverb.IndexOf(substring1));

Console.WriteLine(proverb.IndexOf(substring2));

Console.WriteLine(proverb.IndexOf(substring1,10));

Console.WriteLine(proverb.LastIndexOf(substring1));

}

}

}

Чтобы консоль не закрывалась, запустите программу сочетанием клавиш Ctrl + F5.

Скачать исходник (C#)

Поделиться в соц. сетях:

Основные функции стандартной библиотеки string.h

Основные функции стандартной библиотеки string.h приведены в таблице.

Функция Описание

char *strcat(char *s1, char *s2)

присоединяет s2 к s1, возвращает s1

char *strncat(char *s1, char *s2, int n)

присоединяет не более n символов s2 к s1, завершает строку символом ‘\0’, возвращает s1

char *strсpy(char *s1, char *s2)

копирует строку s2 в строку s1, включая ‘\0’, возвращает s1

char *strncpy(char *s1, char *s2, int n)

копирует не более n символов строки s2 в строку s1, возвращает s1;

int strcmp(char *s1, char *s2)

сравнивает s1 и s2, возвращает значение 0, если строки эквивалентны

int strncmp(char *s1, char *s2, int n)

сравнивает не более n символов строк s1 и s2, возвращает значение 0, если начальные n символов строк эквивалентны

int strlen(char *s)

возвращает количество символов в строке s

char *strset(char *s, char c)

заполняет строку s символами, код которых равен значению c, возвращает указатель на строку s

char *strnset(char *s, char c, int n)

заменяет первые n символов строки s символами, код которых равен c, возвращает указатель на строку s

Пример использования функций


1234567891011121314151617181920212223242526272829303132333435

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <string.h>int main() {  char m1 = «Первая строка»;  char m2 = «Вторая строка»;  char m3;  system(«chcp 1251»);  system(«cls»);  strncpy(m3, m1, 6);  // не добавляет ‘\0’ в конце строки  puts(«Результат strncpy(m3, m1, 6)»);  puts(m3);  strcpy(m3, m1);  puts(«Результат strcpy(m3, m1)»);  puts(m3);  puts(«Результат strcmp(m3, m1) равен»);  printf(«%d», strcmp(m3, m1));  strncat(m3, m2, 5);  puts(«Результат strncat(m3, m2, 5)»);  puts(m3);  strcat(m3, m2);  puts(«Результат strcat(m3, m2)»);  puts(m3);  puts(«Количество символов в строке m1 равно  strlen(m1) : «);  printf(«%d\n», strlen(m1));  _strnset(m3, ‘f’, 7);  puts(«Результат strnset(m3, ‘f’, 7)»);  puts(m3);  _strset(m3, ‘k’);  puts(«Результат strnset(m3, ‘k’)»);  puts(m3);  getchar();  return 0;}

Результат выполнения

Язык Си

Построение строки по Z-функции[править]

Задача:
Необходимо восстановить строку по Z-функции, считая алфавит ограниченным.

Описание алгоритмаправить

Пусть в массиве хранятся значения Z-функции, в будет записан ответ. Пойдем по массиву слева направо.

Нужно узнать значение . Для этого посмотрим на значение : если , тогда в запишем ещё не использованный символ или последний использованный символ алфавита, если мы уже использовали все символы. Если , то нам нужно записать префикс длины строки . Но если при посимвольном записывании этого префикса в конец строки мы нашли такой (индекс последнего символа строки), что больше, чем длина оставшейся незаписанной части префикса, то мы перестаём писать этот префикс и пишем префикс длиной строки .

Для правильной работы алгоритма будем считать значение равным нулю.

Заметим, что не всегда удастся восстановить строку с ограниченным алфавитом неподходящего размера. Например, для строки массив Z-функций будет . Используя двоичный алфавит, мы получим строку , но её массив Z-функций отличается от исходного. Ошибка восстановления строки возникла, когда закончились новые символы алфавита.

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

Реализацияправить

string buildFromZ(z : int[], alphabet : char[]):
  string s = ""
  int prefixLength = 0 
  int j 
  int newCharacter = 0 
  for i = 0 to z.length - 1
      
      if z = 0 and prefixLength = 0
          if newCharacter < alphabet.length
              s += alphabet
              newCharacter++
          else
              s += alphabet
      
      if z > prefixLength
          prefixLength = z
          j = 0
      
      if prefixLength > 0
          s += s
          j++
          prefixLength--       
  return s

Доказательство корректности алгоритмаправить

Докажем, что если нам дали корректную Z-функцию, то наш алгоритм построит строку с такой же Z-функцией.

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

Записали префикс, начинающийся в . После пишем префикс, начинающийся в . Этот префикс не изменит символы первого префикса.

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

Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются (начало и конец одного префикса не принадлежат другому), один лежит внутри другого (начало и конец префикса принадлежит другому), они пересекаются (начало одного префикса пренадлежит другому, но конец не принадлежит).

Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.

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

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

Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.

Ввод и вывод строк в С

Для ввода и вывода строковой информации можно использовать функции форматированного ввода и вывода (printf и scanf). Для этого в строке формата при вводе или выводе строковой переменной необходимо указать спецификатор типа %s. Например, ввод и последующий вывод строковой переменной будет иметь вид:

char str = «»; printf(«Введите строку: «); scanf(«%30s”,str); printf(«Вы ввели: %s”,str);

Недостатком функции scanf при вводе строковых данных является то, что символами разделителями данной функции являются:

  1. перевод строки,
  2. табуляция;
  3. пробел.

Поэтому, используя данную функцию невозможно ввести строку, содержащую несколько слов, разделенных пробелами или табуляциями. Например, если в предыдущей программе пользователь введет строку: «Сообщение из нескольких слов», то на экране будет выведено только «Сообщение». Для ввода и вывода строк в библиотеке stdio.h содержатся специализированные функции gets и puts.

Функция gets предназначена для ввода строк и имеет следующий заголовок:char * gets(char *buffer);

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

char * fgets(char * buffer, int size, FILE * stream);

где buffer — строка для записи результата, size — максимальное количество байт, которое запишет функция fgets, stream — файловый объект для чтения данных, для чтения с клавиатуры нужно указать stdin. Эта функция читает символы со стандартного ввода, пока не считает n — 1 символ или символ конца строки, потом запишет считанные символы в строку и добавит нулевой символ. При этом функция fgets записывает в том символ конца строки в данную строку, что нужно учитывать.

Функция puts предназначена для вывода строк и имеет следующий заголовок:int puts(const char *string);

Простейшая программа: ввод и вывод строки с использованием функций fgets и puts будет иметь вид:

char str = «»; printf(«Введите строку: «);fgets(str, 102, stdin); printf(«Вы ввели: «); puts(str);

Для считывания одного символа можно использовать функцию fgetc(FILE * stream). Она считывает один символ и возвращает значение этого символа, преобразованное к типу int, если же считывание не удалось, то возвращается специальная константа EOF, равная -1. Функция возвращает значение -1 для того, чтобы можно было обрабатывать ситуацию конца файла, посимвольное чтение до конца файла можно реализовать следующим образом:

int c;while ((c = fgetc(stdin)) != EOF) {    // Обработка символа}

Для вывода одного символа можно использовать функцию  int fputc(int c, FILE *stream);.

Помимо функций ввода и вывода в потоки в библиотеке stdio.h присутствуют функции форматированного ввода и вывода в строки. Функция форматированного ввода из строки имеет следующий заголовок:

int sscanf(const char * restrict buffer, const char * restrict string, …); 

Функции форматированного вывода в строку имеют следующие заголовки:

int sprintf(char * restrict buffer, const char * restrict format, …); int snprintf(char * restrict buffer, size_t maxsize, const char * restrict format, …);


С этим читают