Stack Overflow
Stack Overflow

Questions tagged [string-search]

String searching algorithms (also known as string matching algorithms) are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text.

String searching algorithms (also known as string matching algorithms) are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text.

Use this tag for programming questions related to string searching algorithms.

Source: Wikipedia

261 questions
123
votes
6 answers

Search for selection in Vim

I use Vim and Vim plugins for Visual Studio when writing C++. Often, I find myself wanting to search for a string within a function, for example every call to object->public_member.memberfunc(). I know Vim offers a convenient way to search for a…
Marcin
  • 12,245
  • 9
  • 42
  • 49
81
votes
17 answers

Fastest way to search in a string collection

Problem: I have a text file of around 120,000 users (strings) which I would like to store in a collection and later to perform a search on that collection. The search method will occur every time the user change the text of a TextBox and the result…
etaiso
  • 2,736
  • 3
  • 26
  • 38
63
votes
3 answers

What are the main differences between the Knuth-Morris-Pratt and Boyer-Moore search algorithms?

What are the main differences between the Knuth-Morris-Pratt search algorithm and the Boyer-Moore search algorithm? I know KMP searches for Y in X, trying to define a pattern in Y, and saves the pattern in a vector. I also know that BM works better…
ghaschel
  • 1,313
  • 3
  • 20
  • 41
38
votes
4 answers

Case insensitive string search in golang

How do I search through a file for a word in a case insensitive manner? For example If I'm searching for UpdaTe in the file, if the file contains update, the search should pick it and count it as a match.
user3841581
  • 2,637
  • 11
  • 47
  • 72
37
votes
8 answers

Change foreign characters to their roman equivalent

I am using php and I was wondering if there was a predefined way to convert foreign characters to their non-foreign alternatives. Characters such as ê, ë, é all resulting to 'e'. I'm looking for a function that would take a string and return it…
ThomasReggi
  • 55,053
  • 85
  • 237
  • 424
33
votes
2 answers

Boyer Moore Algorithm Understanding and Example?

I am facing issues in understanding Boyer Moore String Search algorithm. I am following the following document. Link I am not able to work out my way as to exactly what is the real meaning of delta1 and delta2 here, and how are they applying this to…
AGeek
  • 5,165
  • 16
  • 56
  • 72
28
votes
4 answers

Java equivalent of C#'s 'Enumerable.Any'

In C# there is a way of reducing the length of an if-statement by using Enumerable.Any to check if elements in a sequence satisfy a condition (https://msdn.microsoft.com/en-us/library/vstudio/bb534972%28v=vs.100%29.aspx). For example Instead of: If…
Mirodinho
  • 1,171
  • 1
  • 13
  • 25
22
votes
7 answers

How to find best fuzzy match for a string in a large string database

I have a database of strings (arbitrary length) which holds more than one million items (potentially more). I need to compare a user-provided string against the whole database and retrieve an identical string if it exists or otherwise return the…
guillermooo
  • 7,915
  • 15
  • 55
  • 58
21
votes
3 answers

php - Is strpos the fastest way to search for a string in a large body of text?

if (strpos(htmlentities($storage->getMessage($i)),'chocolate')) Hi, I'm using gmail oauth access to find specific text strings in email addresses. Is there a way to find text instances quicker and more efficiently than using strpos in the above…
Bob Cavezza
  • 2,810
  • 7
  • 38
  • 56
14
votes
4 answers

Search specific string and return whole line

What I would like to do is find all instances of a string in a text file, then add the full lines containing the said string to an array. For example: eng GB English lir LR Liberian Creole English mao NZ Maori Searching eng, for…
apophis
  • 269
  • 1
  • 3
  • 7
14
votes
3 answers

When is Rabin Karp more effective than KMP or Boyer-Moore?

I'm learning about string searching algorithms and understand how they work but haven't found a good enough answer about in which cases Rabin-Karp algorithm would be more effective than KMP or Boyer-Moore. I see that it is easier to implement and…
E.K
  • 315
  • 1
  • 3
  • 6
14
votes
1 answer

What is the Time Complexity, Space complexity and Algorithm for strstr() function in C++?

I was curious about the cost of using the default, old fashioned strstr() function in C++. What is its Time and Space complexity? Which algorithm does it use? We have other algorithms with below Worst Case Time and Space complexity : Let n = length…
Prasath Govind
  • 720
  • 2
  • 10
  • 30
11
votes
1 answer

MySQL: How to search multiple tables for a string existing in any column

How can I search for in table_a table_b table_c, which have a random number of columns for a string? I know this is not proper sql but it would be something like: SELECT * FROM users, accounts, something_else WHERE ->ANY COLUMN CONTAINS…
fmsf
  • 36,317
  • 49
  • 147
  • 195
10
votes
2 answers

Making MySQL IN Clause Case Sensitive

Does anyone know how I can make an IN clause behave in a case sensitive manner? I have seen that COLLATE can be used with LIKE for string searching but I don't know if or how it can be used with IN. For example I want to do something like SELECT *…
hackartist
  • 5,172
  • 4
  • 33
  • 48
9
votes
1 answer

String searching algorithms

For the two string searching algorithms: KMP and suffix tree, which is preferred in which cases? Give some practical examples.
avd
  • 13,993
  • 32
  • 78
  • 99
1
2 3
…
17 18