Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a sub-string of $y$ is much smaller than $n$.
A trivial algorithm would be this:
1. foreach x in L:
2. foreach y in L:
3. if x is substring of y:
4. OUTPUT x,y
However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm?
Edit: As pointed out in the comments, there can be at most $n^2$ such pairs, so I don't see how there can be an algorithm faster than $O(n^2)$. However, I was wondering if there is something like a $P-FPT$ algorithm where the squared complexity is dependent on the number of output pairs, rather than $n$? Or at least an algorithm that reduces the complexity to something better than $O(n^2 \cdot m)$.