Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [string-matching]

The tag has no usage guidance.

-3
votes
0answers
37 views

Which algorithm is better and why : Rabin-Karp or KMP [closed]

I'm looking for why Rabin-karp is better than KMP and vice versa and where one is more useful in any said scenario. Please could someone explain or point me in the right direction?
1
vote
0answers
64 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 ...
2
votes
3answers
201 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 ...
2
votes
0answers
103 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 ...
1
vote
1answer
126 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 ...
2
votes
4answers
372 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....
1
vote
1answer
1k 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: ...
6
votes
2answers
1k 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, ...
-5
votes
2answers
221 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 (...
20
votes
7answers
17k 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 ...
3
votes
3answers
101 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,...
2
votes
3answers
868 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 ...
7
votes
2answers
236 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, ...
0
votes
1answer
1k 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 ...
6
votes
4answers
2k 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 ...
23
votes
5answers
2k 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. ...
-1
votes
1answer
582 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 ...
3
votes
2answers
588 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 ...
4
votes
2answers
882 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 ...
1
vote
0answers
196 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 ...
0
votes
0answers
520 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 ...
0
votes
2answers
164 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 ...
0
votes
0answers
827 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, ...
1
vote
1answer
76 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 ...
0
votes
1answer
129 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 ...
3
votes
2answers
511 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 ...
5
votes
2answers
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 * ...
2
votes
1answer
994 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 "...
0
votes
0answers
167 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 ...
2
votes
3answers
4k 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,...
1
vote
2answers
4k 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 ...
3
votes
4answers
2k 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" ...
2
votes
0answers
162 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 ...
2
votes
1answer
170 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 ...
2
votes
6answers
2k 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 "?" and ...