What algorithm may be used to solve the re-assembly of shredded papers?
If the cuts are in the middle of letters, then I think your solution in the last paragraph is a good one.

If the cuts go between letters, then I think your approach of finding pairs of strips of papers is a good one.  I would start by finding all pairs of strips that could have been adjacent, based on which digraphs (pairs of characters) can appear in some word.  Then, I would try to extend to find all triples of strips that could have been adjacent: for each possible pair of adjacent strips $s_1,s_2$, find all $s_3$ such that $s_2,s_3$ is a pair of possible adjacent strips; then test whether if you past together $s_1,s_2,s_3$ that all trigraphs (triples of characters) can appear in some word.  Then, I would extend to 4-tuples of strips, filtering them based on 4-graphs of characters, and so on.  The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good.

For fun, you might enjoy reading about the DARPA shredding challenge (summary on Wikipedia).