Questions tagged [string-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
37 votes
7 answers
48k views

What algorithm would you best use for string similarity?

I am designing a plugin to uniquely identify content on various web pages, based on addresses. So I may have one address which looks like: 1 someawesome street, anytown, F100 211 later I may find ...
Squiggs.'s user avatar
  • 511
24 votes
5 answers
3k views

Is there any good search algorithm for a single character?

I know several basic string-matching algorithms such as KMP or Boyer-Moore, but all of those analyze the pattern before searching.However, if one has a single character, there is not much to analyze. ...
Christian's user avatar
  • 365
7 votes
2 answers
269 views

Finding and counting equal substrings in a set of strings

I'm thinking about a way of finding similar parts in Strings. I have a set of strings of varying length i.e: The quick brown fox jumps fox force five the bunny is much quicker than the fox is First, ...
Chris's user avatar
  • 207
6 votes
4 answers
6k views

Is "use "abc".equals(myString) instead of myString.equals("abc") to avoid null pointer exception" already problematic in terms of business logic?

I heard numerous times that when comparing Strings in Java, to avoid null pointer exception, we should use "abc".equals(myString) instead of myString.equals("abc"), but my question is, is this idea ...
ggrr's user avatar
  • 5,775
6 votes
2 answers
4k views

Detecting plagiarism – what algorithm?

I'm currently writing a program to read a body of text and compare it to search-engine results (from searching for substrings of the given text), with the goal of detecting plagiarism in, for example, ...
Vivian's user avatar
  • 189
5 votes
2 answers
1k views

Any reasons why SQL-92 changed *, ? into %, _?

Do you know any reasons why SQL-92 standard has changed glob pattern wildcard characters from * and ? (SQL-89) to % and _? Currently I need to do mask conversions to allow users searching data with * ...
miroxlav's user avatar
  • 672
4 votes
2 answers
2k views

why regex, when using global search and {0,} quantifier, match the end of the string?

I have asked a question here about js, regex, quantifiers and global search. I've understood finally how this works, but, let's take a concrete example and then I`ll write my question. Based on the ...
Gigi Ionel's user avatar
3 votes
2 answers
882 views

String Searching algorithm

A title for a movie can be ambiguous. (Eg. The Lord of the Rings, Lord of the Rings, Lord of the Rings, The) There exists a database entry that has a list of movie titles mapped to a unique ...
Theheist1992's user avatar
3 votes
4 answers
3k views

fast n-gram access data structure

TL;DR Is there a data structure that'd quickly let me match words at any point (e.g., 'foo' matches 'foobar' and 'zoofoo'), and, ideally, returns a list of "characters that show up after the needle" ...
Tordek's user avatar
  • 454
3 votes
3 answers
129 views

Replace strings based on substring match

I have N strings and M search-replace pairs. Each of the strings contains exactly one of the search pair and the whole string needs to be replaced by the replace pair. Say you have returns,between,...
chx's user avatar
  • 373
3 votes
2 answers
1k views

Burrows-Wheeler transform backward search: how to find suffix index?

BWT backward search algorithm is pretty straightforward if we only need the multiplicity of a pattern. However I also need to find the suffix indices (i.e. positions in the reference string where a ...
user798275's user avatar
3 votes
0 answers
198 views

String and Suffix Matching from a Suffix List

I'm having trouble finding an algorithm that matches (or fails to match) a substring of a string to a suffix from a list of suffixes. The hits I'm finding are for suffix trees and suffix arrays, but ...
user avatar
2 votes
4 answers
2k views

What is the optimal way to perform 5000 unique string replace functions in terms of performance?

Restructuring some code, and the way I built it up over time has portions that look something like this: s.replace("ABW"," Aruba "); s.replace("AFG"," Afghanistan "); s.replace("AGO"," Angola "); s....
Anon's user avatar
  • 3,593
2 votes
6 answers
3k views

Find pattern in a string [closed]

How would one approach the following question: We have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?&...
Chander Shivdasani's user avatar
2 votes
3 answers
6k views

Can regexp be used to check for palindromes?

Can regexp pattern matching be used to check for palindromes within a given text in Java? My intuition is that in order to check for palindromes, we may need to remember the character that was parsed,...
GermanShepherd's user avatar
2 votes
3 answers
1k views

Algorithm to find maximum matched units

I will try to explain my objective with an example which will be easier to understand. Suppose I have a sentence like "A B C D E F G H".(Each word seperated using single space). I have a Database ...
Nagaraju's user avatar
2 votes
1 answer
4k views

Efficient multiple substrings search

I have many substrings(2-5 words each) which I would like to search in some text of about 40-50 words length. What is the most efficient way to flag matching substrings. Currently I am simply using: ...
skadoosh's user avatar
  • 121
2 votes
2 answers
536 views

Are there typo-tolerance algorithms (as opposed to string similarity)? [closed]

I want to build a search with basic typo tolerance. There are quite a few string similarity algorithms (and implementations for almost all languages I guess). However, humans tend to make some typos ...
cis's user avatar
  • 255
2 votes
3 answers
1k views

Algorithm for optimizing text compression

I am looking for text compression algorithms (natural language compression, rather than compression of arbitrary binary data). I have seen for example An Efficient Compression Code for Text ...
Lance's user avatar
  • 2,587
2 votes
1 answer
1k views

Matching algorithms in context of data quality problems

I work for an organization that has lots of databases containing person information. The data quality is poor. One case was a surname I found like this (this is the worst-case scenario): Mark "...
w0051977's user avatar
  • 7,081
2 votes
1 answer
194 views

Comparing strings against a pool of words

I am creating an app where the user enters 8 characters. After he enters the string I have to see if it is an eight letter word. If not, check if contains a seven letter word etc. I am checking ...
Ivan Crojach Karačić's user avatar
2 votes
0 answers
217 views

Algorithm to search very long blacklist in another very long data set

I have two data sets. The first data set has approx. 50.000 movie and song titles and the second one have 20.000 blacklist strings. I am looking for the best algorithm to detect movie/song title which ...
Eray's user avatar
  • 336
1 vote
1 answer
167 views

Find a string in list of strings

Background: I am writing an application for a small embedded device. There is a static list of strings: currently about 500 strings and string length is 12 characters on average. The list might ...
psy's user avatar
  • 137
1 vote
2 answers
6k views

Filtering common starting/ending characters from array/list of strings

Ok so for example I have an array of strings with each string as below: 364VMS1029 364VMSH920 364VMSH192 364VMSU839 364VMN2382 364VMR223 364VMR2X3 364VMN829 364VMN8757 364VMN831 How can I ...
user3373225's user avatar
1 vote
1 answer
86 views

Why try to match for nth negatives, as opposed to matching lesser positives?

My Title clearly indicated my lack of understanding about the core concept for pattern matching - specifically using .HTACCESS to block Bad-Bots from accessing a site, which they do in order to crawl ...
user avatar
1 vote
0 answers
197 views

Name matching in SWIFT messages

Here i am basically looking for performance improvement. I need to match names in a SWIFT message (Let's say MT 103) against sanctions lists (sanctions lists by UN, by OFAC, some custom lists) and ...
bjan's user avatar
  • 229
1 vote
0 answers
166 views

phonetic algorithms for words that aren't surnames?

I've been doing a little research into algorithms for matching spelling mistakes in names. From Soundex through to metaphone and Beider-Morse. All of these algorithms generally focus on last names ...
Jarede's user avatar
  • 323
1 vote
0 answers
360 views

clustering of strings with variable-length prefixes

I've got bunch of strings with variable-length prefixes (or postfixes - I can always revert them) as follows: 0155555555 523455555555 755555555 ... 87129999999999999 119999999999999 09119999999999999 ...
god's user avatar
  • 232
0 votes
2 answers
174 views

Is there a approximate string comparison function which is odd like mathematical functions are odd?

I say odd like a mathematical function, a mathematical function is odd if f(-x) = -f(x) I understand that comparing two strings may seem to have little to do with this, because the arguments cannot ...
iharob's user avatar
  • 111
0 votes
1 answer
164 views

What's the algorithm should I use for seeing how well 2 strings match?

Suppose I have 2 strings: string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3" string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3" string4 = "Music/Jim Smith/Unknown/00 ...
Nona's user avatar
  • 101
0 votes
1 answer
205 views

Data Matching In VBA - Best way to deal with dynamic data and user entry?

Background I am currently building this project with VBA, just to keep in the back of your mind when thinking about my question. Imagine 2 adjacent blocks, in Excel. The first block is made up of ...
Ekko's user avatar
  • 17
0 votes
1 answer
2k views

Most Pythonic way to remove first match of potential leading strings?

This is a bit difficult to describe, but I'll do my best. In Python, I can use string.startswith(tuple) to test for multiple matches. But startswith only returns a boolean answer, whether or not it ...
Hactar's user avatar
  • 115
0 votes
0 answers
605 views

scrabble solving with maximum score

I was asked a question You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word out ...
dharakk's user avatar
0 votes
0 answers
1k views

Compare names and the use of Levenshtein's algorithm

I need to cross names from two lists. What is the best away to compare the names? As you may expect, in one list we can have the complete name, on the other just the first and last. Besides that, ...
cap7's user avatar
  • 287
0 votes
0 answers
243 views

Similar problem to word break

I have a list of strings say L and an array of words say A. I want to find a string from the list L that is a best match to a string created from the permutations of the words in the array. The ...
Viraj's user avatar
  • 111
-1 votes
1 answer
1k views

Find missing number in sequence in string [closed]

I have a string that contains numbers in sequence. There are no delimiters between numbers. I have to find missing number in that sequence. For example: 176517661768 is missing the number: 1767 ...
Neo's user avatar
  • 31
-1 votes
3 answers
226 views

Is there a text distance (or string similarity) algorithm which accounts for the distance between characters?

I'm interested in finding a text distance (or string similarity) algorithm which computes a greater distance (or lower similarity) when characters are further apart. For example, I want the distance ...
Vermillion's user avatar
-6 votes
2 answers
321 views

Which piece of code is more efficient with respect to Time and Memory cost? [closed]

Code 1: private static int myCompare(String a, String b) { /* my version of the compareTo method from the String Java class */ int len1 = a.length(); int len2 = b.length(); if (...
Avid Programmer's user avatar