0
votes
0answers
32 views

Search substring using suffix array (and LCP)

I'm searching for a best way to improve suffix array run time using LCP. My text (about 2 500 000 chars) seems like: 0ricco0eric0america0polo0.... My thoughs: SA=suffixArray char=firstChar(input) s ...
1
vote
1answer
86 views

Algorithm to create permutations for a given alphabet based on a sequence number

I would like to have a function that will create a word (always the same word) for a given sequence number based on a given alphabet. word(0, [a,b,c]) = a word(1, [a,b,c]) = b word(2, [a,b,c]) = c ...
0
votes
0answers
38 views

Algorithm for HIghest Local Alignment Score with a specific character match between two subsequences

I'm writing a code that identifies the highest-scoring local alignment between a substring X' of X and a substring Y' of Y that has at least one column in which a C from X' is aligned to a W from Y'. ...
1
vote
0answers
123 views

What is the purpose of chunking strings in natural language processing?

I see many examples of libraries that use a 'chunker' and also people asking how to write chunkers, but what is this for and why do we need it? Isn't it enough to split a text by whitespace or other ...
1
vote
1answer
109 views

Search Substring in String collection

I have a big collection of strings a[1], …, a[N] where N is about several millions. I am provided a string m and I need to iterate over all the strings a[i] that contain m. In other words, I need to ...
2
votes
1answer
116 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 ...
8
votes
1answer
223 views

Match two strings but allow for a degree of error

How can I match two strings, but at the same time allow for X number of characters to be incorrect in the match. The number of errors should be a controllable variable. While X number of characters ...
0
votes
4answers
466 views

What does it mean to perform an operation “In Place” for Interpreted Languages?

Programming question: Reverse words in a string (words are separated by one or more spaces). Now do it in-place. What does "in-place" mean in the above context for an interpreted language ...
8
votes
1answer
610 views

Possible Damerau-Levenshtein improvement?

I recently implemented the Damerau-Levenshtein distance algorithm from the pseudocode on Wikipedia. I couldn't find any explanation of exactly how it works and the pseudocode uses completely ...
7
votes
3answers
429 views

Longest subsequence without string

Does there exist a dynamic programming algorithm to find the longest subsequence in a string X that does not contain Y as substring? Just that this problem seems so similar to other DP string ...
0
votes
1answer
198 views

Algorithm Identification [ String & Dictionary ]

I recently heard of an interview question: Given a string and a dictionary. Break the string into meaningful words and I remember solving this before with dynamic programming fairly quickly (maybe ...
6
votes
2answers
3k views

Which string search algorithm is actually the fastest?

I have been stuck for some time on which is the fastest string search algorithm, heard many opinions, but in the end I'm not sure. I have heard some people saying that the fastest algorithm is ...
1
vote
2answers
358 views

Looking for a non-cryptographic hash function that returns a single character

Suppose I have a dictionary of ASCII words stored in uppercase. I also want to save those words into separate files so that the total word count of each file is approximately the same. By simply ...
6
votes
1answer
3k views

Shortest Common Superstring: find shortest string that contains all given string fragments

Given some string fragments, I would like to find the shortest possible single string ("output string") that contains all the fragments. Fragments can overlap each other in the output string. ...
10
votes
6answers
2k views

Is it inefficient to concatenate strings one at a time?

I recall back from my days of programming in C that when two strings are joined, the OS must allocate memory for the joined string, then the program can copy all the string text over to the new area ...
1
vote
4answers
139 views

Possible applications of algorithm devised for differentiating between structured vs random text

I have written a program that can rapidly (within 5 sec on a 2GB RAM desktop, 2.33 Ghz CPU) differentiate between structured text (e.g English text) and random alphanumeric strings. It can also ...
8
votes
5answers
3k views

How can I extract words from a sentence and determine what part of speech each is? [closed]

I want to write something that takes a sentence and identifies each word it contains and defines what part of speech each word is. For example Hello World, I am a sentence would return this ...
11
votes
2answers
325 views

How to select a most probable option from the list based on user text Input

I am working over a OCR Application where I need to select a option based on user text input. Ex: Available Options: ["python", "ruby", "java", "clojure", "haskell"] Input: kava Output: java Input: ...
1
vote
3answers
916 views

Search for a sub-string in a given array of strings

I have an array of n strings. I want to select all the elements of the array that starts with the given string. Sorry if that is not clear. I'll give an example. input = "as" array = ["abas", ...