Как найти поиск текста в строке

В этой статье описаны синтаксис формулы и использование функций НАЙТИ и НАЙТИБ в Microsoft Excel.

Описание

Функции НАЙТИ и НАЙТИБ находят вхождение одной текстовой строки в другую и возвращают начальную позицию искомой строки относительно первого знака второй строки.

Важно: 

• Эти функции могут быть доступны не на всех языках.

• Функция НАЙТИ предназначена для языков с однобайтовой кодировкой, а функция НАЙТИБ — для языков с двухбайтовой кодировкой. Заданный на компьютере язык по умолчанию влияет на возвращаемое значение указанным ниже образом.

• Функция НАЙТИ при подсчете всегда рассматривает каждый знак, как однобайтовый, так и двухбайтовый, как один знак, независимо от выбранного по умолчанию языка.

• Функция НАЙТИБ при подсчете рассматривает каждый двухбайтовый знак как два знака, если включена поддержка языка с БДЦС и такой язык установлен по умолчанию. В противном случае функция НАЙТИБ рассматривает каждый знак как один знак.

К языкам, поддерживающим БДЦС, относятся японский, китайский (упрощенное письмо), китайский (традиционное письмо) и корейский.

Синтаксис

НАЙТИ(искомый_текст;просматриваемый_текст;[нач_позиция])

НАЙТИБ(искомый_текст;просматриваемый_текст;[нач_позиция])

Аргументы функций НАЙТИ и НАЙТИБ описаны ниже.

• Искомый_текст    — обязательный аргумент. Текст, который необходимо найти.

• Просматриваемый_текст    — обязательный аргумент. Текст, в котором нужно найти искомый текст.

• Начальная_позиция    — необязательный аргумент. Знак, с которого нужно начать поиск. Первый знак в тексте «просматриваемый_текст» имеет номер 1. Если номер опущен, он полагается равным 1.

Замечания

• Функции НАЙТИ и НАЙТИБ работают с учетом регистра и не позволяют использовать подстановочные знаки. Если необходимо выполнить поиск без учета регистра или использовать подстановочные знаки, воспользуйтесь функцией ПОИСК или ПОИСКБ.

• Если в качестве аргумента «искомый_текст» задана пустая строка («»), функция НАЙТИ выводит значение, равное первому знаку в строке поиска (знак с номером, соответствующим аргументу «нач_позиция» или 1).

• Искомый_текст не может содержать подстановочные знаки.

• Если find_text не отображаются в within_text, find и FINDB возвращают #VALUE! значение ошибки #ЗНАЧ!.

• Если start_num не больше нуля, то найти и найтиБ возвращает значение #VALUE! значение ошибки #ЗНАЧ!.

• Если start_num больше, чем длина within_text, то поиск и НАЙТИБ возвращают #VALUE! значение ошибки #ЗНАЧ!.

• Аргумент «нач_позиция» можно использовать, чтобы пропустить нужное количество знаков. Предположим, например, что для поиска строки «МДС0093.МесячныеПродажи» используется функция НАЙТИ. Чтобы найти номер первого вхождения «М» в описательную часть текстовой строки, задайте значение аргумента «нач_позиция» равным 8, чтобы поиск в той части текста, которая является серийным номером, не производился. Функция НАЙТИ начинает со знака 8, находит искомый_текст в следующем знаке и возвращает число 9. Функция НАЙТИ всегда возвращает номер знака, считая от левого края текста «просматриваемый_текст», а не от значения аргумента «нач_позиция».

Примеры

Скопируйте образец данных из следующей таблицы и вставьте их в ячейку A1 нового листа Excel. Чтобы отобразить результаты формул, выделите их и нажмите клавишу F2, а затем — клавишу ВВОД. При необходимости измените ширину столбцов, чтобы видеть все данные.

Данные
Владимир Егоров
Формула	Описание	Результат
=НАЙТИ(«В»;A2)	Позиция первой «В» в ячейке A2	1
=НАЙТИ(«в»;A2)	Позиция первой «в» в ячейке A2	6
=НАЙТИ(«и»;A2;3)	Позиция первой «и» в строке А2, начиная с третьего знака	8

Пример 2

Данные
Керамический изолятор №124-ТД45-87
Медная пружина №12-671-6772
Переменный резистор №116010
Формула	Описание (результат)	Результат
=ПСТР(A2;1;НАЙТИ(» №»;A2;1)-1)	Выделяет текст от позиции 1 до знака «№» в строке («Керамический изолятор»)	Керамический изолятор
=ПСТР(A3;1;НАЙТИ(» №»;A3;1)-1)	Выделяет текст от позиции 1 до знака «№» в ячейке А3 («Медная пружина»)	Медная пружина
=ПСТР(A4;1;НАЙТИ(» №»;A4;1)-1)	Выделяет текст от позиции 1 до знака «№» в ячейке А4 («Переменный резистор»)	Переменный резистор

Найти подстроку в строке

Алгоритм поиска строки Бойера — Мура — алгоритм общего назначения, предназначенный для поиска подстроки в строке.

Давайте попробуем найти вхождение подстроки в строку.

Наш исходный текст будет:

Text: somestring

И паттерн, который мы будем искать

Pattern: string

Давайте расставим индексы в нашем тексте, чтобы видеть на каком индексе находится какая буква.

0 1 2 3 4 5 6 7 8 9
s o m e s t r i n g

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

int find (string text, string pattern){}

В нашем примере должно будет вернуться 4.

           0 1 2 3 4 5 6 7 8 9
text:      s o m e s t r i n g
pattern:           s t r i n g

Если ответ не найден, мы будем возвращать -1

int find (string text, string pattern) {   
int t = 0; создадим индекс для прохода по тексту.   
int last = pattern.length — 1; это индекс последнего элемента в шаблоне

Создадим цикл для прохода по тексту.

while (t < text.length — last)

Почему именно такое условие? Потому что если останется символов меньше чем длина нашего паттерна, нам уже нет смысла проверять дальше. Наш паттерн точно не входит в строку.

В нашем примере:

last = 5 (Последний индекс паттерна string равен 5)

Длина текста равна 10 (somestring)

Это значит что text.length — last = 10–5 = 5;

           0 1 2 3 4 5 6 7 8 9
text:      s o m e s t r i n g
pattern:           s t r i n g     

Можно заметить, что если мы стоим на 5м индексе в строке, а 4й не подошел, то наш паттерн не входит в строку, например

            0 1 2 3 4 5 6 7 8 9
text:       s o m e X t r i n g                      
                    ^
pattern:            s t r i n g

Получится что длина паттерна, больше чем длина оставшейся строки.

На данный момент у нас есть код вида :

int find (string text, string pattern) {   
int t = 0;   
int last = pattern.length — 1;   
	while (t < text.length — last){  
	}
}

Теперь введем переменную int p = 0, которая будет двигаться по нашему паттерну.

И запустим внутренний цикл

while( p <= last && text[ t + p ] == pattern[p] ){
}

p <= last — пока меньше или равно последнему индексу символа шаблона

text[ t + p ] = pattern[p] — пока очередной сивмол текста совпадает с символом в шаблоне.

Давайте детальнее разберем, что значит text[ t + p ] = pattern[p]

Допустим мы в тексте стоим на индексе 4

              0 1 2 3 4 5 6 7 8 9
text:         s o m e s t r i n g                      
                      ^     
pattern:              s t r i n g

Получается t = 4, p = 0; text[ t + p ] = text[ 4 + 0 ] = s, pattern[0] = s, значит условие цикла выполняется.

Код на текущий момент:

int find (string text, string pattern) {   
int t = 0;   
int last = pattern.length — 1;   
	while (t < text.length — last) {      
  	int p = 0;      
    	while( p <= last && text[ t + p ] = pattren[p] ){         
      Если условие цикла выполняется, сдвигаем p вперед.         
      	p ++;      
      }         
      В результате если p == pattern.length 
      мы можем вернуть индекс на котором паттерн входит в текст.      
      	if (p == pattern.length){         
        	return t;      
      	}      
      В противном случае идем к следующему индексу в строке.      
      t ++;   
      }
   }

Получается мы имеем такой метод:

int find (string text, string pattern) {   
	int t = 0;   
	int last = pattern.length — 1;   
  	while (t < text.length — last) {      
    	int p = 0;      
      while( p <= last && text[ t + p ] == pattern[p] ) {
      	p ++;      
      }   
      if (p == pattern.length) {
      	return t;   
       }   
       t ++;   
     }   
   return — 1;
}

Как можно ускорить этот алгоритм? Какие есть варианты?

Представим что у нас в тексте есть символ, которого нет в паттерне.

text: some*string , то на сколько можно сдвигать паттерн?

А если есть повторяющиеся символы?

Например можно начать бежать с конца паттерна, то есть

text:     somestring               
               ^ 
pattern:  string               
               ^

Начинаем бежать с конца паттерна. Если символы не совпадают, на сколько можно сдвинуть паттерн?

Если символ из текста есть в нашем паттерне, то можно сразу сдвинуть до этого символа.

text:    somestring
pattern:     string

Сдвигаем на длину паттерна минус индекс символа на котором мы стоим в тексте.

То есть в данном случае

text: somestring           
           ^
pattern: string              
              ^

Когда мы начинаем бежать по паттерну с конца у нас pattern[i] = ‘g’, а text[i] = ’t’,

мы можем сдвинуть наш паттерн на pattern.length — индекс ’t’ в паттерне.

Индекс ’t’ в паттерне = 1, получается 5–1 = 4, сдвигаем паттерн на 4 символа вперед.

text:         somestring                       
                       ^
pattern:      >>>>string                       
                       ^

Мы можем предварительно создать таблицу для нашего паттерна.

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

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

Таблица смещений:
s 0
t 1
r 2
i 3
n 4
g 5
* -1

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

pattern: колокол
к 4
л 2 — если символ последний в строке, то оставляем его первый вход
м -1
н -1
о 5

Мы сдвигаем на последние вхождение символа, потому что если сдвигать на первое, то можно упустить часть входа паттерна в строку.

Попробуем реализовать эту часть алгоритма:

int[] createOffsetTable(string pattern) {   
	int[] offset = new int[128]; // количество символов зависит от 
  // алфавита с которым мы работаем   
  for (int i = 0; i < offset.length; i++){
  	offset[i] = -1; // заполняем базовыми значениями   
  }   
  for (int i = 0; i < pattern.length; i++){
  	offset[pattern[i]] = i;   
  }   
  return offset;
}

Добавим таблицу смещений в алгоритм поиска, что мы написали выше:

int find (string text, string pattern) {   
	int[] offset = createOffsetTable(pattern);   
  int t = 0;   
  int last = pattern.length — 1;   
  while (t < text.length — last){
  	int p = last; // начнем двигаться с конца паттерна
    //Чуть чуть меняем условие цикла, 
    //так как теперь мы двигаемся с конца      
    while( p >= 0 && text[ t + p ] == pattern[p] ){
    	p — ;      
    }      
    if (p == -1){
    	return t;      
    }      
    t += last — offset[ text[ t + last ] ];   
  }   
  return — 1;
}

Почему t + last ? Смотрим на каком символе стоим в тексте и прибавляем длину шаблона. Если при поиске входа, какая то часть не совпала, то мы должны сдвинуться на символ текста в котором стоим + длина шаблона.

Например:

Таблица смещений для колокол:
к = 4
л = 2
о = 5

Шаг 1:

         0 1 2 3 4 5 6 7 8 9 10
text:    а а к о л о л о к о л о к о л
pattern: к о л о к о л
last = 7; 
t += last — offset[text[t + last]]
t += last — offset[text[0 + 7]]
t += last — offset[‘о’]
t += 7–5 = 2;
t = 2;

Шаг 2:

         0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:    а а к о л о л о к о л о к о л
pattern: > > к о л о к о л
t = 2;
t += last — offset[text[t + last]]
t += last — offset[text[2 + 7]]
t += last — offset[‘о’]
t += 7–5 = 2;
t = 4;

Шаг 3:

         0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:    а а к о л о л о к о л о к о л
pattern: > > > > к о л о к о л
t = 4;
t += last — offset[text[t + last]]
t += last — offset[text[4 + 7]]
t += last — offset[‘о’]
t += 7–5 = 2;
t = 6;

Шаг 4:

         0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:    а а к о л о л о к о л о к о л
pattern: > > > > > > к о л о к о л
t = 6;
t += last — offset[text[t + last]]
t += last — offset[text[6 + 7]]
t += last — offset[‘о’]
t += 7–5 = 2;
t = 8;

Шаг 5:

         0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:    а а к о л о л о к о л о к о л
pattern: > > > > > > > > к о л о к о л

Совпадение найдено.

На этом разбор упрощенного алгоритма Бойера-Мура закончен.

Пока мы отталкивались только от крайних символов. Но возможно ли как то использовать информацию по уже пройденным символам?

Допустим есть строка

abcdadcd

Как составить таблицу смещений мы уже знаем. Теперь составим таблицу суффиксов.

Когда мы стоим на символе d, на сколько можно сдвинуть паттерн? Сдвигаем на на расстояние до ближайшего такого же символа. В примере ниже у нас есть 2 символа d с расстояниями 2 и 4. Мы выберем 2 потому что оно меньше.

            4   
          -----—    
          |   2   
          | ---   
          | | |
       abcdadcd       
       ^

Дальше рассмотрим суффикс cd. Для d мы уже записали 2.

       2
abcdadcd 
У нас есть только один суффикс cd, это значит что можно          
-- сдвинуться на 4 символа. 
Запишем для с = 4.   

     842
abcdadcd 
Далее dcd. dcd в тексте больше нигде не встречается.         
--- Двигаем на длину шаблона = 8

И для всех остальных символов пишем 8, потому что суффиксы не будут совпадать.

Теперь вернемся к нашему паттерну колокол.

колокол* В конце всегда будет *, еcли символ не совпал, сдвинем на 1.

              1
       колокол*       
              —       
             41
       колокол*      
             -—      
            441
       колокол*     
            --—     
           4441
       колокол*    
           ---—     
           4441
       колокол*    
           ----

Для окол мы тоже запишем 4. Потому что у нас префикс совпадает с суффиксом.

Попробуем написать код для этого

createSuffix(string pattern){   
	int[] suffix = new int[pattern.length + 1]; // +1 для символа звездочки   
  	for(int i = 0; i < pattern.length; i ++){
    	suffix[i] = pattern.length; // изначальное значение, 
      //длина шаблона. на сколько сдвигать если нет совпадения суффиксов   
    }   
    suffix[pattern.length] = 1; // для звездочки ставим 1
    //Сначала создадим переменную, которая идет справа на лево.   
    for (int i = pattern.length — 1; i >= 0; i — ) {
    	for (int at = i; at < pattern.lenth; at ++){
      	string s = pattern.substring(at); // с какого символа берем подстроку

Например колокол с чем сравниваем?

        --— 
    колокол   
    	 --—  
      --- 
    ---
   ---

кол мы сравним с око, лок, оло, кол         

for (int j = at — 1; j >= 0; j — ) {
	string p = pattern.substring(j, s.length); // берем подстроку той же длинны
  //что и суффикс            
  if (p.equals(s)) { 
  	suffix[j] = at — i; 
    break;            
  }        
 }      
 }   
 }   
 return suffix;}

Существует более оптимальный алгоритм, но дальше индивидуально.

Какой код у нас есть на данный момент?

int[] createSuffix (string pattern) {   
	int[] suffix = new int[pattern.length + 1];   
  	for (int i = 0; i < pattern.length; i ++){
    	suffix[i] = pattern.length;   
    }   
    suffix[pattern.length] = 1;   
    for (int i = pattern.length — 1; i >=0; i — ){
    	for(int at = i; i < pattern.length; i ++){
      	string s = pattern.substring(at);         
        for (int j = at — 1; j >= 0; j — ){
        	string p = pattern.substring(j, s.length);
          if (p == s) {
          	suffix[i] = at — 1;
            at = pattern.length;
            break; 
          }        
        }      
      }  
    }   
    return suffix;
  }
  
int find(string text, string pattern) {   
	int[] offset = createOffset(pattern);   
  int[] suffix = createSuffix(pattern);   
  int t = 0;   
  int last = pattern.length — 1;   
  while (t < text.length — last) {
  	int p = last;      
    	while (p >= 0 && text[t + p] == pattern[p]) { 
      	p — ;    
      }      
    	if (p == -1) {
      	return t;
      }      
      t += Math.max (p — offset[text[t + p]], suffix[p + 1]);   
    }   
  return -1;
}

p — prefix[text[t + p]] — последний символ, который нашли и под него подстроить сдвиг нашего шаблона

suffix[p + 1] — значение суффикса для последнего элемента, который был сравнен.

И двигаем на максимальное значение, чтобы двигаться максимально быстро.

На этом разбор алгоритма Бойера-Мура закончен. Спасибо за внимание! =)

В этой статье поговорим про строки в Python, особенности поиска, а также о том, как искать подстроку или символ в строке.

Но сначала давайте вспомним основные методы для обработки строк в Python:
• isalpha(str): если строка в Python включает в себя лишь алфавитные символы, возвращается True;
• islower(str): True возвращается, если строка включает лишь символы в нижнем регистре;
• isupper(str): True, если символы строки в Python находятся в верхнем регистре;
• startswith(str): True, когда строка начинается с подстроки str;
• isdigit(str): True, когда каждый символ строки — цифра;
• endswith(str): True, когда строка в Python заканчивается на подстроку str;
• upper(): строка переводится в верхний регистр;
• lower(): строка переводится в нижний регистр;
• title(): для перевода начальных символов всех слов в строке в верхний регистр;
• capitalize(): для перевода первой буквы самого первого слова строки в верхний регистр;
• lstrip(): из строки в Python удаляются начальные пробелы;
• rstrip(): из строки в Python удаляются конечные пробелы;
• strip(): из строки в Python удаляются и начальные, и конечные пробелы;
• rjust(width): когда длина строки меньше, чем параметр width, слева добавляются пробелы, строка выравнивается по правому краю;
• ljust(width): когда длина строки в Python меньше, чем параметр width, справа от неё добавляются пробелы для дополнения значения width, при этом происходит выравнивание строки по левому краю;
• find(str[, start [, end]): происходит возвращение индекса подстроки в строку в Python. В том случае, если подстрока не найдена, выполняется возвращение числа -1;
• center(width): когда длина строки в Python меньше, чем параметр width, слева и справа добавляются пробелы (равномерно) для дополнения значения width, причём происходит выравнивание строки по центру;
• split([delimeter[, num]]): строку в Python разбиваем на подстроки в зависимости от разделителя;
• replace(old, new[, num]): в строке одна подстрока меняется на другую;
• join(strs): строки объединяются в одну строку, между ними вставляется определённый разделитель.

Обрабатываем строку в 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


Поиск подстроки в строке
Чтобы в Python выполнить поиск в строке, используют метод find(). Он имеет три формы и возвращает индекс 1-го вхождения подстроки в строку:

• find(str): поиск подстроки str производится с начала строки и до её конца;

• find(str, start): с помощью параметра start задаётся начальный индекс, и именно с него и выполняется поиск;

• find(str, start, end): посредством параметра end задаётся конечный индекс, поиск выполняется до него. 

Когда подстрока не найдена, метод возвращает -1:
    welcome = "Hello world! Goodbye world!"
index = welcome.find("wor")
print(index)       # 6

# ищем с десятого индекса
index = welcome.find("wor",10)
print(index)       # 21

# ищем с 10-го по 15-й индекс
index = welcome.find("wor",10,15)
print(index)       # -1


Замена в строке
Чтобы в Python заменить в строке одну подстроку на другую, применяют метод replace():

• replace(old, new): подстрока old заменяется на new;

• replace(old, new, num): параметр num показывает, сколько вхождений подстроки old требуется заменить на new.
Пример замены в строке в Python:
    phone = "+1-234-567-89-10"

# дефисы меняются на пробелы
edited_phone = phone.replace("-", " ")
print(edited_phone)     # +1 234 567 89 10

# дефисы удаляются
edited_phone = phone.replace("-", "")
print(edited_phone)     # +12345678910

# меняется только первый дефис
edited_phone = phone.replace("-", "", 1)
print(edited_phone)     # +1234-567-89-10


Разделение на подстроки в Python
Для разделения в Python используется метод split(). В зависимости от разделителя он разбивает строку на перечень подстрок. В роли разделителя в данном случае может быть любой символ либо последовательность символов. Этот метод имеет следующие формы:

• split(): в роли разделителя применяется такой символ, как пробел;

• split(delimeter): в роли разделителя применяется delimeter;

• split(delimeter, num): параметром num указывается, какое количество вхождений delimeter применяется для разделения. При этом оставшаяся часть строки добавляется в перечень без разделения на подстроки.
Соединение строк в Python
Рассматривая простейшие операции со строками, мы увидели, как объединяются строки через операцию сложения. Однако есть и другая возможность для соединения строк — метод join():, объединяющий списки строк. В качестве разделителя используется текущая строка, у которой вызывается этот метод:
words = ["Let", "me", "speak", "from", "my", "heart", "in", "English"]

# символ разделителя - пробел
sentence = " ".join(words)
print(sentence)  # Let me speak from my heart in English

# символ разделителя - вертикальная черта
sentence = " | ".join(words)
print(sentence)  # Let | me | speak | from | my | heart | in | English


А если вместо списка в метод join передать простую строку, разделитель будет вставляться уже между символами:
word = "hello"
joined_word = "|".join(word)
print(joined_word)      # h|e|l|l|o