Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?
This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted. 

First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because the same string can match $m$ times in the worst case. (For example ab matches ababab 3 times.)



This can be improved to true linear $O(L + M)$ time, where $L$ is the total length of the strings and $M$ is the number of matches:

When running the strings through the automaton, store for each node of the automaton the index of the previous string for which this node was visited. When outputting the matches, stop following the dictionary links if the link leads to a node that has already been visited for this string - you have already outputted all matches that are upwards from that node. Now each match gets outputted exactly once, and we traverse dictionary links only when new matches are outputted.