Как называется поиск по первым буквам

Задача о наибольшей подпоследовательности-палиндроме

Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.

Задача:

Задача о наибольшей подпоследовательности-палиндроме — это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной последовательности таким образом, что оставшаяся подпоследовательность будет палиндромом.

Решение

Обозначим данную последовательность через [math]S[/math] , а ее элементы — через [math]S[i], 0 \leqslant i \leqslant n — 1[/math] , где [math]n[/math] — длина строки [math]S[/math] . Будем рассматривать возможные подпоследовательности данной последовательности с [math]i — [/math] го по [math]j — [/math] ый символ включительно, обозначив её как [math]S(i, j)[/math] . Длины максимальных подпалиндромов для данной последовательности будем записывать в двумерный массив [math]L[/math] : [math]L[i][j][/math] — длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности [math]S(i, j)[/math] .

Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида [math]S(i, i)[/math] ) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов [math]S(i, i + 1)[/math] возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.

Пусть теперь нам дана подпоследовательность [math]S(i, j)[/math] . Если [math]S[i][/math] и [math]S[j][/math] элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность [math]S(i, j — 1)[/math] или [math]S(i + 1, j)[/math] — то есть мы сведем задачу к подзадаче: [math]L[i][j] = \max(L[i][j — 1], L[i + 1][j])[/math] . Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи [math]S(i + 1, j — 1):L[i][j] = L[i + 1][j — 1] + 2[/math] . Таким образом получаем следующее рекуррентное соотношение:

[math] L[i][j] = \begin 1, & i = j\\ 0, & i \gt j\\ L[i + 1][j — 1] + 2, & s[i] = s[j] \\ \max(L[i][j — 1], L[i + 1][j]), & s[i] \neq s[j] \end [/math]

Асимптотика

Каждый элемент массива мы вычисляем [math]1[/math] раз за [math]O(1)[/math] обращаясь к уже вычисленным элементам. Так как размер массива [math]n \times n[/math] , то алгоритм работает за [math]O(n^2)[/math]

Пример

Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями [math]S(i, i)[/math] из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме [math]S(3, 4)[/math] , элементы различны, поэтому в соответствующие ячейки запишем [math]1[/math] , а в [math]L[3][4][/math] — [math]2[/math] .

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины [math]3[/math] получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому [math]L[0][2] = L[1][1] + 2[/math] . В остальных подпоследовательностях первый и последний элементы различны.

BAC: [math]L[1][3] = \max(L[1][2], L[2][3]) = 1[/math]

ACC: [math]L[2][4] = \max(L[2][3], L[3][4]) = 2[/math]

CCB: [math]L[3][5] = \max(L[3][4], L[4][5]) = 2[/math]

CBA: [math]L[4][6] = \max(L[4][5], L[5][6]) = 1[/math]

Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке [math]L[0][6][/math] получим ответ — [math]6[/math] .

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

Последовательность заполнения массива и массив переходов см. на изображениях ниже.

Псевдокод

Перед вызовом процедуры заполняем [math]L[][][/math] начальными значениями: [math]L[i][j] = 1[/math] если [math]i=j[/math] , [math]L[i][j] = 0[/math] , если [math]i\gt j[/math] , в остальных случаях [math]L[i][j]=-1[/math] . При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной [math] N [/math] вызов функции будет иметь следующий вид: [math] \mathrm[/math] . Искомая же длина будет записана в ячейке [math]L[0][N-1][/math] .

Функция для вычисления длины палиндрома:

Границы исходной последовательности: [math] \mathtt[/math]

int palSubSeq(left: int, right: int): if L[left][right] == -1 if s[left] == s[right] L[left][right] = palSubSeq(left + 1, right - 1) + 2 else L[left][right] = max(palSubSeq(left + 1, right), palSubSeq(left, right - 1)) return L[left][right]

Процедура для построения искомого палиндрома:

Границы исходной последовательности: [math] \mathtt[/math]
Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: [math] \mathtt[/math]

// palindrome — массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома palChars(left: int, right: int, palLeft: int, palRight: int): while left [math]\leqslant [/math] right if left == right and L[left][right] == 1 palindrome[palLeft++] = S[left++] else if S[left] == S[right] palindrome[palLeft++] = S[left++] palindrome[palRight--] = S[right--] else if L[left + 1][right] [math] \gt [/math] L[left][right - 1] left++ else right--

См. также

Задача о наибольшей общей подпоследовательности
Задача о наибольшей возрастающей подпоследовательности
Задача о наибольшей общей палиндромной подпоследовательности

Источники информации

Википедия — Палиндром
Wikipedia — Palindrome
Wikipedia — Longest palindromic subsequence

Поиск файлов в директории по первым буквам их имен

Вообщем проблема вот в чем — Есть текстбокс который называется «Поиск». Короче смысл такой же как и у эксплорера. банальный поиск файла в конкретной директории по первым буквам. А в идеале так же как и в ХР — можно в названии файла, а можно и в самом файле. Вывод будет в ListView, но это я уж сам сделаю, не проблема.

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Поиск имен в Dictionary по первым двум буквам
Задание такое: "В отпуске Вася не тратил время зря, а заводил новые знакомства. Он знакомился с.

Поиск и автоматический переход в списке по первым буквам их имен
Добрый вечер . Имеется форма по коду или названию выбираем товар и заносим в таблицу . Как.

Поиск слова по первым 5 буквам
Есть база слов, все слова разной длинны, находятся в текстовом документе на раб. столе. Я открываю.

Поиск по первым буквам в StringGrid
Здравствуйте есть база данных StringGrid, есть поиск , но как сделать что бы искало по первым.

1080 / 1007 / 106
Регистрация: 28.02.2010
Сообщений: 2,889
Пример поиска. То что нужно найти — ineedthis.

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 29 30 31 32 33 34 35 36

using System; using System.Collections.Generic; using System.IO; class Program { static Liststring> lst; static string ineedthis; static void Main(string[] args) { lst = new Liststring>(); ineedthis = "readme_en.txt"; search("Z:\\"); for (int i = 0; i  lst.Count; i++) { Console.WriteLine(lst[i]); } } static void search(string dir) { string[] subdirs = Directory.GetDirectories(dir); string[] foundfiles = Directory.GetFiles(dir, ineedthis); for (int i = 0; i  foundfiles.Length; i++) { lst.Add(foundfiles[i]); } for (int i = 0; i  subdirs.Length; i++) { search(subdirs[i]); } } }

2364 / 1242 / 78
Регистрация: 28.10.2009
Сообщений: 4,331
kOS_77, примерно так, только вместо ListView используется ListBox

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

Imports System.IO Public Class Form1 Dim dir As String Dim dirInfo As DirectoryInfo Private Sub TextBox2_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles TextBox2.TextChanged ListBox1.Items.Clear() If TextBox2.Text = "" Then Exit Sub For Each fileIn As FileInfo In dirInfo.GetFiles() If fileIn.Name.StartsWith(TextBox2.Text) Then ListBox1.Items.Add(fileIn.Name) End If Next End Sub Private Sub TextBox1_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles TextBox1.TextChanged dir = TextBox1.Text If Directory.Exists(dir) Then TextBox2.Enabled = True dirInfo = New DirectoryInfo(dir) Else MessageBox.Show("Эта папка не существует") End If End Sub End Class

Программка в прикреплении
Вложения

FileSearch.zip (9.6 Кб, 54 просмотров)

Как организовать поиск по первым буквам запроса через input javascript

Прилагаю свой вариант, но он работает только для первого символа, дальше не получается организовать вывод (только начала изучать javascript).

1 2 3 4 5 6 7 8 9 10 11

document.getElementById('termDropList').innerHTML = ''; for (var i = 0; i  terms.length; i++) { var A = String.fromCharCode(event.keyCode).toLowerCase(); var B = terms[i]; if (A.charCodeAt(0) === B.charCodeAt(0)) { document.getElementById('termDropList').innerHTML += ' + B + ''; } }

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Как сделать поиск по первым буквам слов?
Делаю поиск по буквам. При вводе в эдит буквы "в" в таблице выводит и иванова, и петрова, и.

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

Поиск по первым буквам слова
Добрый день. Подскажите пожалуйста код для поиска по первым буквам слова. В компонент tableView_5.

2169 / 1652 / 840
Регистрация: 10.01.2015
Сообщений: 5,186
Не совсем понятно задание. Пока как пример. Вероятно, поможет.

1 2 3 4

var arr = ['фыв','пыв','выв','фвап']; for (var i = 0; i  arr.length; i++){ if(arr[i][0] === 'ф') console.log(arr[i]); //вернет фыв и фвап }

Регистрация: 19.11.2016
Сообщений: 10

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

Эксперт JS Эксперт HTML/CSS Эксперт PHP

1846 / 1342 / 599
Регистрация: 12.01.2011
Сообщений: 5,432

div id='result'>/div> input type='search' id='search' placeholder="Текст">

1 2 3 4 5 6 7 8 9 10 11 12 13

var arr = ['add','remove','classlist','lol','sap','sanek','left','width'] document.getElementById('search').onkeyup = function(){ document.getElementById('result').innerHTML = ''; var l = this.value.length; if(l>0){ for(var i=0;iarr.length;i++){ var _ = arr[i].split('').slice(0,l).join(''); if(_==this.value){ document.getElementById('result').innerHTML+=arr[i]+'
'; } } } };

Регистрация: 19.11.2016
Сообщений: 10

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

Необходимо чтобы после ввода символов из масива подбирались элементы, присутствующие в нём. У меня получилось сделать только для первого символа, далее при вводе (к примеру, «ау») ничего не показывает, но должно показывать аудио.

Надеюсь я более ясно изъяснилась. Благодарю за ответы!

Эксперт JS Эксперт HTML/CSS Эксперт PHP

1846 / 1342 / 599
Регистрация: 12.01.2011
Сообщений: 5,432

Лучший ответ

Сообщение было отмечено John_cher как решение

Решение

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

Добавлено через 20 минут

Цитата Сообщение от John_cher Посмотреть сообщение

У меня получилось сделать только для первого символа
А у меня показывает введите например a а потом au
https://jsfiddle.net/2k08moeo/4/
Регистрация: 19.11.2016
Сообщений: 10
Большое Вам спасибо, все получилось!
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Поиск слова по первым 5 буквам
Есть база слов, все слова разной длинны, находятся в текстовом документе на раб. столе. Я открываю.

Поиск по первым буквам из формы!
Есть массив, в нём имена. Надо чтобы "что-то" выводило те имена у которых начало на букву "А". .

Поиск записей в списке по первым буквам
всем привет. вопрос конечно глупый, но не тривиальный. на форме Главная есть список0 со.

Поиск по первым буквам в классе Dictionary
Привет всем! В общем есть пара вопросов: 1) как сделать поиск по первым словам в слове как на.