The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
78 views

Count distinct and same substrings in a range

Given a string T with n lowercase letters T[1..n]. For each substrings T[l..r], we can assign them two values, k1 and k2, which are defined as following. K1 is the number of different ...
3
votes
1answer
107 views

String matching for all suffixes

Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ ...
4
votes
1answer
64 views

Suffix trees - “smaller half trick”

I have been reading a paper Finding Maximal Pairs with Bounded Gap: An in there, there is a sentence (page 6 second paragraph): The “smaller-half trick” is used in several methods for finding ...
9
votes
1answer
514 views

Counting number of sums from contiguous subarrays of an array

We are given an array $a[1 \ldots n]$ with all $a[i]>0$. Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., ...
1
vote
1answer
1k views

Number of distinct substrings in a string

From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$. The answer can be obtained by $$ ...
8
votes
2answers
5k views

Computing the longest common substring of two strings using suffix arrays

After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two ...