69 questions
1
vote
1
answer
118
views
Efficient Approach to Decompressed String Substring Problem
The problem involves decompressing a compressed string and outputting the substring in the range of L and R. For example:
A(BB(CC)) -> ABBCCCCBBCCCC
L = 52, R = 60,
((((((((IMTOOSTRONG)))))))) -&...
- 21
0
votes
0
answers
167
views
Getting Levenshtein distance from `diifflib.ndiff`
The levenshtein distance algorithm in Python is too slow as I am comparing many strings.
So I want to use difflib.ndiff to do it.
I tried parsing the output by interpreting "+", "-"...
- 165
2
votes
2
answers
703
views
How to do multiple sequence alignment of text strings (utf8) in R
Given three strings:
seq <- c("abcd", "bcde", "cdef", "af", "cdghi")
I would like to do multiple sequence alignment so that I get the following ...
- 581
2
votes
0
answers
256
views
Equivalence of Edit Distance and Alignment Distance
(from: https://math.mit.edu/classes/18.417/Slides/alignment.pdf)
The slide on the 11th page talks about how the Edit Distance and the Alignment Distance are equivalent.
I understand how to prove that ...
- 31
1
vote
1
answer
104
views
Extract JPA Named Parameters in Javascript
I am trying to extract JPA named parameters in Javasacript. And this is the algorithm that I can think of
const notStrRegex = /(?<![\S"'])([^"'\s]+)(?![\S"'])/gm
const ...
- 33
0
votes
1
answer
103
views
Which character to append to string in suffix array?
I was solving
https://www.spoj.com/problems/BEADS/
above question at SPOJ. I have stated the relevant information below:
Problem Statement:
The description of the necklace is a string A = a1a2 ... am ...
- 211
0
votes
0
answers
136
views
KMP algorithm with blank letter in pattern
can someone suggest me how to make Knuth–Morris–Pratt algorithm which contains "blank letter" in pattern text?
At the input you get pattern and text, where in the pattern ? character can ...
1
vote
2
answers
1k
views
Can someone explain this "Longest Common Subsequence" algorithm?
The Longest Common Subsequence (LCS) problem is: given two sequences A and B, find the longest subsequence that is found both in A and in B. For example, given A = "peterparker" and B = &...
- 1,023
1
vote
0
answers
260
views
Find optimal alignment between 2 strings with gap cost function
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
Given two strings S1 and S2, find the ...
- 1,081
6
votes
3
answers
1k
views
Find longest adjacent repeating non-overlapping substring
(This question isn't about music but I'm using music as an example of
a use case.)
In music a common way to structure phrases is as a sequence of notes
where the middle part is repeated one or more ...
- 20.7k
0
votes
1
answer
78
views
Proof for minimum number of String Rotation Problem
Let's say we are rotating a string one at a time ("abcd" -> "bcda"). After some t rotations we get the same string. Let t be the minimum such number of rotations.
For ex:
For S = "aaaa", t = 1
For S =...
- 3
4
votes
2
answers
252
views
Algorithm for finding bags of elements in a sequence
Say that I have a sequence of elements of interest A, B, C... interspersed with don't care symbols x. I want to identify bags of elements from a predefined set of interesting combinations that happen ...
- 4,795
1
vote
1
answer
291
views
Is there a method in Java that will replace the first occurrence of a String with a given String? [duplicate]
I am trying to write a madlibs program in Java. There is a method that takes a template String, an ArrayList of all the placeholders in that String, and an ArrayList of all the user inputs that will ...
- 830
-2
votes
2
answers
4k
views
Finding all the shortest unique substring which are of same length?
Given a string sequence which contains only four letters, ['a','g','c','t']
for example: agggcttttaaaatttaatttgggccc.
Find all the shortest unique sub-string of the string sequence which are of equal ...
0
votes
3
answers
200
views
How to write a string algorithm
given a FASTA text file (Rosalind_gc.txt), I am supposed to go through each DNA record and identify the percentage (%) of Guanine-Cytosine (GC) content.
Example of this is :
Sample Dataset:
>...
0
votes
1
answer
154
views
Fuzzy search over millions of strings with custom distance function
I have a large pool of short strings and a custom distance function on them (let's say Damerau–Levenshtein distance).
Q: What is the state-of-the-art solution for getting top N strings from the pool ...
- 9,049
1
vote
0
answers
269
views
Checking whether an array is a suffix array for any binary string
I'm currently trying to figure out whether a given array, which is a permutation of the numbers 1 to n, is a suffix array of any binary string.
For example for n = 3, A = {2, 1, 3} is valid, since ...
- 143
1
vote
1
answer
2k
views
I would like my bot to delete the message that contains a keyword or that contains similar characters
in my bot I have implemented a keyword filter that the bot reviews in each message that is written in the chat, until now it works, but I want to improve it, for reasons of respect I will not put ...
- 27
4
votes
4
answers
226
views
Find all concatenations of two string in a huge set
Given a set of 50k strings, I need to find all pairs (s, t), such that s, t and s + t are all contained in this set.
What I've tried
, there's an additional constraint: s.length() >= 4 && ...
- 46.8k
0
votes
1
answer
254
views
How can I implement array list input for string similarity algorithm?
I implemented jarowinkler algorithm. In that algorithm I have taken string source and string target. String target taking as input string source taking as array like source[0]. How can implement ...
4
votes
1
answer
193
views
How to find number of 010 in a certain range of a binary string
Given a binary string. How to find occurances of "010" within a certain range of the string.For example, I have the string "0100110" . If the given range is 3 7 ( 1 based indexing ) then the output ...
- 112
0
votes
2
answers
347
views
Rank of string solution
I was going through a question where it asks you to find the rank of the string amongst its permutations sorted lexicographically.
O(N^2) is pretty clear.
Some websites have O(n) solution also. The ...
- 5,355
2
votes
1
answer
1k
views
KMP Algorithm for string search?
I found this very challenging coding problem online which I though I'd give a try.
The general idea is that given string of text T and pattern P, find the occurrences of this pattern, sum up it's ...
user7947407
4
votes
3
answers
7k
views
C++ Find last ocurrence of a string inside a substring
I need a method that helps me to find a string inside another substring, or in other words, find a string inside a subrange of other string. Besides, I need to find it in reverse order because I know ...
- 12.5k
0
votes
0
answers
142
views
N-gram extractor
I want to solve a following algorithmic problem. Given a set of strings s1, s2, ..., sn. I want to find a string s_e, which contains all n-grams, which exist in all input string.
Consider an example ...
- 1,819
1
vote
0
answers
695
views
String Alignment in haskell
I'm working on an assignment in Haskell.
The assignment is to give the optimal alignment of two strings given scores for word matches, misses and gap insertions.
Here is our code so far. The first ...
0
votes
2
answers
1k
views
Count the number of occurrences of a character in a string for a number of queries?
I want to find the occurrences of a character in a string for n queries:
For example the string is: "i_love_mathematics"
and the task is to find the occurrence of:
'i' in range:
1-4(a ...
- 1,421
0
votes
3
answers
193
views
An optimized algorithm or a method to find a multi word string (keywords) in a sentence (that has multi words)?
I have a string (Hello this is a string) and i want to search a keywords in it. How shall i do it ?
I have to search the following keywords in a string:
String: Hello this is a string.
Keywords:
1. ...
- 27
1
vote
1
answer
2k
views
How to find most frequent substrings in a string using Bash?
Please, how to solve the following problem:
How to find the most frequent substrings in a given string? For example the string:
...
- 13
3
votes
3
answers
7k
views
How to convert a string to a palindrome with minimum number of character replacement such that palindromic string contains a given word?
We have a string s, containing lower case alphabets (a-z). We can replace any character with any other character, and we can do this any number of times.
We can to make a palindrome string p from s, ...
- 2,592
2
votes
3
answers
4k
views
palindromes count swift optimization
Hey i have a question about optimization palindromes count algorithm
Task: Find count of palindromes in string.
in my func i use "in the forehead" method its like O(n^2)
can you guys help make it ...
- 119
-2
votes
1
answer
161
views
How to find the number of distinct sub strings of n strings?
Given n strings each of length <=10^5.
Input: “aa ab ac ad”
Output: 8 (“a”,”b”,”c”,”d”,”aa”,”ab”,”ac”,”ad”)
Input: “aab bcd”
Output: 10 (“a”,”b”,”c”,”d”,”aa”,”ab”,”bc”,”cd”,”aab”,”bcd”)
update:...
- 311
0
votes
0
answers
168
views
Concept clarity - wavelet tree
How a wavelet tree can be used for storing integer-ids. Say for example integer-ids collection be (1,2,3,4,5,6,7,8,9,10). Could any one explain how it works?
General wavelet tree construction looks ...
- 13
14
votes
4
answers
2k
views
Find substring in text which has the highest similarity to a given keyword
Say I have this text = I love apples, kiwis, oranges and bananas and the searchString = kiwis and bananas and a similarity algorithm say Jaccard index. How can I efficiently find the substring in text ...
- 33.7k
10
votes
3
answers
2k
views
Fast substring search algorithm to be used by a sort of IDE with tens of thousands of very big files
I'm developing something quite similar to an IDE that will handle tens of thousands of very large (text) files and I'm surveying what the state of the art in the subject is.
As an example, Intellij's ...
- 106k
0
votes
0
answers
487
views
How to use LCP and suffix array to find the maximum number of occurrences of a given pattern in a string?
I am trying to solve this problem on how to search for a given pattern in a string using LCP and suffix array, but I am not able to solve the part on how I can find the number occurrences of that ...
- 181
4
votes
3
answers
6k
views
python str.index time complexity
For finding the position of a substring, inside a string, a naive algorithm will take O(n^2) time. However, using some efficient algorithms (eg KMP algorithm), this can be achieved in O(n) time:
s = '...
- 6,808
-3
votes
1
answer
811
views
Algorithm to find all substrings from the given array of string
I need to find all sub-strings from the given array of strings and group them.
Additional condition:
If string S1 contains string S2, S1 contains S3, S2 contains S4 - all them should be in one group....
- 8,854
3
votes
4
answers
2k
views
Python3 Fast Way To Find If Any Elements In Collections Are Substring Of String
If I have a collection of strings is there a data structure or function that could improve the speed of checking if any of the elements of the collections are substrings on my main string?
Right now ...
- 5,250
1
vote
1
answer
788
views
Simple solution for Isomorphic string check which just coulnd't pass 1 test case
The following is my solution for Isomorphic string problem given in leetcode:
public bool IsIsomorphic(string s, string t)
{
int[] s1 = new int[s.Length];
int[] t1 = new int[t....
- 225
0
votes
3
answers
160
views
Python coding relating to function any and "more than once" keyword
I have this simple piece of code that tells me if a word in a given list appears in an article:
if not any(word in article.text for word in keywords):
print("Skipping article as there is no ...
- 131
-1
votes
4
answers
451
views
Split String into groups [closed]
I've a string like this Delete File/Folder. I need to break the sentence based on the / equivalent to or.
Finally need to generate two strings out of this like Delete File as one string and Delete ...
- 191
-1
votes
2
answers
248
views
Find all permitation for list or word list in very long text
Given the word list = { w1,w2,w3,w1,w2 }
Find all permutations of above word list in long text.
long text list = {This is long text w1 w2 w3 w4 and w1 w2 w1 w2 w3. This yet another long text ...
- 670
1
vote
3
answers
2k
views
Inplace string replacement in C
Write a function
void inplace(char *str,
const char pattern,
const char* replacement,
size_t mlen)
Input:
str: a string ending with \0. the input indicates ...
- 2,877
1
vote
0
answers
59
views
minimum reduced string made up of a,b,c [duplicate]
This is an interview questions asked from me.
An input string is made up of only a, b and c. You have to reduce the string to minimum possible length. Reducing criteria is:
if ab or ba comes ...
- 1,188
0
votes
1
answer
1k
views
Find the most similar subsequence in another sequence
I need to write an algorithm, that finds the most similar substring in S1 to another string S2 (substring in S1 that has minimum Hamming distance with S2, in other words) in N log(N), where N = len(S1)...
2
votes
4
answers
4k
views
Remove all the occurences of substrings from a string
Given a string S and a set of n substrings. Remove every instance of those n substrings from S so that S is of the minimum length and output this minimum length.
Example 1
S = ccdaabcdbb
n = 2
...
- 3,298
2
votes
5
answers
7k
views
how to count single or double quotes
my problem is to be able to count the number of single or double quotes in a string in c.
example
String Single Quote Count Double Quote Count
'hello world' ...
- 1,768
1
vote
1
answer
326
views
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.
- 11
0
votes
3
answers
592
views
Python: more readable list comprehension
I am new to Python. I have the following code which is a part of a string algorithm that i'm currently developing.
>>> newlist=[]
>>> i =0
>>> for x in range(len(list1)):
...
- 2,452