Questions tagged [longest-prefix]
29 questions
39
votes
31 answers
Find the longest common starting substring in a set of strings
This is a challenge to come up with the most elegant JavaScript, Ruby or other solution to a relatively trivial problem.
This problem is a more specific case of the Longest common substring problem. I need to only find the longest common starting…
mislav
- 14,919
- 8
- 47
- 63
11
votes
4 answers
Longest Prefix Matches for URLs
I need information about any standard python package which can be used for "longest prefix match" on URLs. I have gone through the two standard packages http://packages.python.org/PyTrie/#pytrie.StringTrie & 'http://pypi.python.org/pypi/trie/0.1.1'…
Amit
- 614
- 1
- 8
- 18
9
votes
2 answers
How to use a Trie data structure to find the sum of LCPs for all possible substrings?
Problem Description:
References: Fun With Strings
Based on the problem description, a naive approach to find sum of length of LCP for all possible substrings (for a given string) is as follows :
#include
#include
using…
Saurabh P Bhandari
- 6,014
- 1
- 19
- 50
4
votes
1 answer
Runtime of KMP algorithm and LPS table construction
I recently came across the KMP algorithm, and I have spent a lot of time trying to understand why it works. While I do understand the basic functionality now, I simply fail to understand the runtime computations.
I have taken the below code from the…
user2128105
- 41
- 2
4
votes
5 answers
Longest common prefix and suffix of arrays
What is the best way to get the longest common prefix (sub-array that starts from index 0 of the original) and suffix (sub-array that ends with index -1 of the original) of two arrays? For example, given two arrays:
[:foo, 1, :foo, 0, nil, :bar,…
sawa
- 165,429
- 45
- 277
- 381
2
votes
2 answers
Longest common prefix length of all substrings and a string
I found similar questions on StackOverflow, but my question is different.
Given a string s contains lowercase alphabet. I want to find the length of Longest common Prefix of all substrings.
For example
s = 'ababac'
Then substrings are as follow:
1:…
PRATEEK AGRAWAL
- 319
- 1
- 5
- 17
2
votes
2 answers
Perl: best way to do longest prefix match (string)
I have a list of around 5000 words. I want to find the longest prefix match among those words for a given word. For example, in my list I have :
1
121
12234
20345
21345
Now If I search for 12134 the result will be 121 (longest match). I know it can…
Kamrul Khan
- 3,260
- 4
- 32
- 59
2
votes
4 answers
How to interpret an IP address block?
If I have a block of private IP addresses such as 171.58.0.0/12, does this mean that I essentially bitwise AND the 32-bit version of 171.58.0.0 with 32 bits of 1's, the last 12 of which are 0'd out, to get the longest prefix of acceptable private IP…
atp
- 30,132
- 47
- 125
- 187
1
vote
2 answers
All Common Subsequences in Array of Strings
I'm trying to find ALL common subsequences in an array of strings in ruby not just the longest single subsequence.
This means that if the input is
["aaaF hello", "aaaG hello", "aaaH hello"]
The expected output is
["aaa", " hello"]
I've been…
user1026817
- 51
- 4
1
vote
1 answer
Longest Common Prefix string
Below is my recursive approach to finding the longest common prefix to a set of strings.
package recursion;
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] str) {
String finalStr =…
Sunit Mishra
- 23
- 5
1
vote
1 answer
Elasticsearch PHP longest prefix match
I am currently using the FOSElasticaBundle in Symfony2 and I am having a hard time trying to build a search to match the longest prefix.
I am aware of the 100 examples that are on the Internet to perform autocomplete-like searches using this.…
Benjamin Vison
- 469
- 9
- 20
1
vote
4 answers
Can you use the browser specific prefix in front of all css tags?
Can you use the browser specific prefix in front of all standard tags?
e.g.
#div{
padding:20px;
-moz-padding-bottom:10px;
}
is the above valid CSS for ensuring Firefox has a different bottom padding to all other browsers?
Mazatec
- 11,481
- 23
- 72
- 108
1
vote
1 answer
LCP array for Suffix Array
How to compute the LCP array for a suffix array? It doesn't have to be the most efficient. O(n log n) or O(n) will do. Something relatively easy to code if possible.
user3415207
- 11
- 2
1
vote
1 answer
Implementing Longest Common Substring using Suffix Array
I am using this program for computing the suffix array and the Longest Common Prefix.
I am required to calculate the longest common substring between two strings.
For that, I concatenate strings, A#B and then use this algorithm.
I have Suffix Array…
user3080029
- 553
- 1
- 8
- 19
1
vote
1 answer
Longest Prefix Match
What's the best way to get accurate and fast queries in PostgreSQL for a longest prefix match?
Is it:
A.) select * from table where column in (subselect) ;
B.) select * from table where strpos(column,column2) = 1
order by length(column2) desc…
JPT
- 55
- 4