I have the following problem :

I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an array of char. So if I want to get the factor $w_i...w_j$ of $w$ I need to do a loop that begin at $i$ all the way to up $j$., so it basically takes$O(j-i)$ times. Yet I am doing this operation on a lot of couples $(i,j)$ so at the end it becomes heavy in time complexity.

So one idea is to first calculate all factors of $w$ and put them in a double array of size $\mid w \mid^2$, I guess it takes $O(\mid w \mid^2)$ to fill this array.

Now I am wondering if we can improve this complexity ? Like for example get all factors of $w$ in linear time ? Maybe it's possible to use at first a different data structures to stack $w$ (so not array) that will allowed me to get any factors of $w$ in constant time ?

Thank you !

  • 2
    $\begingroup$ What's a factor of a word? $\endgroup$ – Thumbnail Mar 6 '19 at 17:58

No, there's no faster way to calculate all the "factors" (substrings) of $w$. It takes $\Theta(|w|^2)$ space even to write down the list of all factors. Any algorithm has to spend at least 1 unit of time per character of output. So, any algorithm will have to take $\Omega(|w|^2)$ time; you can't do better than $O(|w|^2)$ time.

If you want to look for a faster algorithm, you'll need to look for a way to do it that doesn't involve calculating and storing all possible factors. You might want to think about what operations you need to perform on these factors, and whether there's any data structure that can help you perform those operations faster (maybe a Merkle hash tree? maybe a rolling hash? hard to know, without knowing what you're trying to do with the factors).

| cite | improve this answer | |
  • $\begingroup$ Thank you for your answer. It makes a lot of sens. I don't know about Merkle hash tree, I am going to look at them to see if it helps :) $\endgroup$ – Name_is_anonyme Mar 6 '19 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.