The string-algorithm tag has no usage guidance.
0
votes
3answers
23 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. ...
1
vote
1answer
32 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:
...
3
votes
2answers
198 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
votes
1answer
50 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:...
2
votes
2answers
77 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 ...
13
votes
4answers
217 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 ...
0
votes
0answers
29 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 ...
6
votes
3answers
78 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 ...
intellij-idea
-2
votes
1answer
72 views
Shortest snippet of strings containing a list of words
I'm working on this problem on google foobar. "Write a function called answer(document, searchTerms) which returns the shortest snippet of the document, containing all of the given search terms. The ...
0
votes
0answers
42 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 ...
2
votes
3answers
61 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 = '...
-4
votes
1answer
89 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....
3
votes
4answers
123 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 ...
0
votes
3answers
57 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 ...
2
votes
4answers
730 views
Remove all the occurances 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
...
1
vote
1answer
67 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....
0
votes
4answers
74 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 ...
-1
votes
2answers
137 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 ...
0
votes
3answers
353 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 ...
3
votes
2answers
1k views
Multiple keyword (100s to 1000s) search (string-search algorithm) in PHP
I have this problem to solve in my PHP project where some keywords (from a few hundreds to a few thousands, lengths can vary) need to be searched in a string about 100-300 characters long, sometimes ...
4
votes
4answers
1k views
Faster Aho-Corasick PHP implementation
Is there a working implementation of Aho–Corasick in PHP? There is one Aho-Corasick string matching in PHP mentioned on the Wikipedia article:
<?php
/*
This class performs a multiple ...
1
vote
0answers
48 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
vote
1answer
172 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.
0
votes
1answer
190 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)...
3
votes
2answers
671 views
In-place replacement of a pattern in a string
In an interview I was asked a question on strings.
The problem is given a string s1= "ABCDBCCDABCD". and a pattern "BC". we have to replace this pattern with other string ("UVW" or "U"or "uv").
This ...
2
votes
1answer
122 views
What is a generalized suffix tree?
I saw the Wikipedia page but still am not clear with the idea.
To find the longest common substring of 2 strings (T and S), I've read that we must build a suffix tree for the string T($1)S($2), where`...
1
vote
5answers
457 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' ...
0
votes
3answers
56 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)):
...
6
votes
2answers
929 views
Alternative to Levenshtein distance for prefixes / suffixes
I have a big city database which was compiled from many different sources. I am trying to find a way to easily spot duplicates based on city name. The naive answer would be to use the levenshtein ...
2
votes
1answer
628 views
How do I use MFC CString with the boost string algorithm library
Preliminary note: string_algo works just fine with std::wstring and of course I can (and do) convert the CString object(s) to std::wstring first if and when I need an algorithm from string_algo. It ...
2
votes
1answer
420 views
Why in C++ function boost::algorithm::join_if a std::bad_cast exception is thrown?
I found a problem in my code. When I use boost::algorithm::join it works normally, but when I use boost::algorithm::join_if a bad_cast is thrown. My code is below:
#include <iostream>
#include &...
1
vote
1answer
133 views
Counting cyclic shifts of a string
I need to write a function that will return the number of possible different cyclic shifts of an input string.
Could you please give me some tips on where should I start in order to create an ...
3
votes
1answer
769 views
Finding a Motif in DNA
Problem can be found here:
http://rosalind.info/problems/subs/
The question I have has to do with the performance of the two solutions provided below.
1.
def indexOfAppearances(strand: String, ...
-2
votes
1answer
95 views
Need an algorithm… not sure what this is called [closed]
Given a string: "ABCD", return the substrings with one or more missing characters keeping the order of the strings. This doesn't seem to be a "permutation", but I'm not sure if this algorithm has a ...
0
votes
0answers
2k views
Algorithm for text justification (flush left and right)
I'm looking to implement a way to perform text justification (flush left and right). Each output line can have a maximum width of M characters. Breaking of words is not allowed.
For example, please ...
3
votes
3answers
274 views
adversary argument for finding n-bit strings
Given:
S, a set an odd number of n-bit strings
A, a particular n-bit string
show that any algorithm that decides whether A is in S must examine all n bits of A in the worst case.
Usually of course ...
2
votes
3answers
2k views
Longest palindrome prefix
How to find the longest palindrome prefix of a string in O(n)?
0
votes
1answer
281 views
Algorithm: String Similarity [closed]
I am trying to solve this challenge on InterviewStreet: https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd
I already have a working algorithm but I would to improve its ...
2
votes
1answer
90 views
Document retrieval with unwanted words
I am building a data structure that helps indexing a collection of S documents of total length n, such that it supports the following query: Given two words P1 and P2, count all the documents that ...
0
votes
1answer
497 views
Searching an array of c-strings for a substring using string_algo/ranges
I need to search an array of c-strings for a substring.
I created what I thought would return me the answer but it is only syntactically correct but semantically wrong, but I'm not sure where I have ...
1
vote
2answers
233 views
How to Store strings to Optimize Searching
I am having a table containing a column of type VARCHAR. I want to search strings inside the column according to user input query. I want to implement Approximate Searching. And my table contains Lacs ...
5
votes
7answers
1k views
Constant-time hash for strings?
Another question on SO brought up the facilities in some languages to hash strings to give them a fast lookup in a table. Two examples of this are dictionary<> in .NET and the {} storage structure ...
11
votes
5answers
2k views
Find the words in a long stream of characters. Auto-tokenize
How would you find the correct words in a long stream of characters?
Input :
"The revised report onthesyntactictheoriesofsequentialcontrolandstate"
Google's Output:
"The revised report on ...
6
votes
5answers
3k views
Books on string algorithms [closed]
There have been numerous posts on string algorithms:
Algorithm to find articles with similar text,
Similar String algorithm,
Efficient string matching algorithm
However, no general literature was ...
Related Tags
algorithm × 29
string × 12
python × 5
data-structures × 4
java × 3
c × 3
search × 3
boost × 3
c# × 2
php × 2
c++ × 2
string-matching × 2
suffix-tree × 2
more related tags
Hot Network Questions
- A world with a special political system
- Is it legal to use Raspberry Pi to develop a product and sell it?
- Was Harry's concern about Fleur's sister Gabrielle misplaced?
- How to distinguish between American Indians and Indian Indians in native English (language) parlance?
- Why isn't Almond Milk (and other non-animal based 'milk') considered juice?
- The codegolf object
- How to tell if your flight has an air-bridge or stairs?
- How do I use mathmode in tables to write physics formulae?
- All Aboard the Kolmogorov Complexity Train
- Can my brother from Australia buy an airline ticket for me?
- How to use breakpoints for debugging
- Who is the tallest?
- How much of my income should I put towards paying off student loans vs saving for a house?
- A paper I received to review has (independently) duplicated work that we are writing up. How to proceed in light of peer-review confidentiality?
- What's the verb for "to drink small amounts of drink"?
- Shortest code to produce non-deterministic output
- Should I defragment my SSD?
- How come the Sun's gravity can hold distant planets in orbit, but cannot rip humans off Earth?
- Am I right to think this homework problem on counting triangles in a grid is improperly set out?
- What does antimatter look like?
- Is it worth sending a manned mission to a black hole?
- Why is Cuba still leasing Guantanamo Bay to the US?
- why are terminal consoles still used?
- Advisor drops MSci student suddenly in final semester
