# Get all factors of a word in linear time or constant time

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 !

• What's a factor of a word? – 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.