# Questions tagged [strings]

Questions about sequences of symbols, sets thereof and their properties as well as uses.

429 questions
Filter by
Sorted by
Tagged with
6 views

### Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because ...
11 views

### Longest palindrome after swapping operation

I know that manachers algorith can be used to find longest palindromic substring of a string in linear time. But I want to find the longest palindromic substring after swapping any two indices once. ...
51 views

### Can a Turing machine start on a blank?

Couldn't find a definitive answer anywhere so asking here. I have a Turing machine and the start state can go straight to the end state without passing through any of the other five states via Blank -...
94 views

### finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
1k views

### Count of distinct substrings in string inside range

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
4k views

### Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
222 views

### Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
167 views

### calculating the string similarity of an optimal alignment

description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
65 views

39 views

### Find the maximum number of contiguous occurrences of smaller string s in a larger string l

Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l. Ex. ...
34 views

### Families of sets indexed by another set

I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets. If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is ...
15 views

### Sorting in computing longest increasing subsequence

I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman. I'm struggling to understand parts of the proof of Theorem 3.5, especially this bit: ...
2k views

### A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
53 views

### Can't wrap my head around on building a suffix table for Boyer Moore

My resources were the following video, as well as this video. Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following: k suffix d2 1 ...
3k views

### Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i,$$ where $b$ is prime (all computations ...
310 views

### Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
158 views

### Find optimal local alignment of two strings with restrictions

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: We want to find an optimal local ...
116 views

### What is the simplest algorithm to compress a string?

I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call ...
91 views

### Time complexity of comparing $N$ strings

I would like to double check myself. As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length). In ...
56 views

### Is string spliting formally defined when the string delimiter is an empty string?

Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you: ...
15 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 ...
43 views

### What is the SetHorspool string searching algorithm and how is it implemented?

What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice? This has been implemented in 2 libraries I have come across: https://app-...
49 views

### Boyer-Moore jump table

I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$ which I want to build a simple jump table for (not considering special optimizing cases for now). I only want to build a jump ...
22 views

### How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated? A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
20 views

### which neural network is good for predecting the value of strings

I have a dataset that contains some strings. A numeric value is assigned to each string. I want to develop a machine learning (deep learning) model to get a string and predict its value. What neural ...
18 views

### Given start strings, find simplest DAG that constructs target strings by concatenation

Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
44 views

2k views

### Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
45 views

### A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
26 views

### How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
43 views

### Finding first occurence of all possible matches?

Say you have multiple strings that you're trying to match in a text. And it's possible all these strings have a match in the text. Is there a good way to return out of all the matching strings the ...
87 views

### Binary string satisfying several constraints

I'm trying to solve this problem, but without success. Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...