Finding interesting anagrams
This problem is known as the “minimum common string partition problem.”  (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.)  Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng [GKZ05].  This means that no polynomial-time algorithm exists unless P=NP.  (Of course, if each letter occurs at most once, then the problem is trivial because there is only one anagramming.)

On the positive side, the same authors [GKZ05] give a polynomial-time 1.1037-approximation algorithm under the same restriction.  (A “1.1037-approximation algorithm” means an algorithm which may not output the correct answer A but is guaranteed to output a value B such that A ≤ B ≤ 1.1037A.)  They also give a linear-time 4-approximation algorithm under the weaker restriction that each letter occurs at most three times in each of the input strings.

[GKZ05] Avraham Goldstein, Petr Kolman, and Jie Zheng.  Minimum common string partition problem: Hardness and approximations.  Electronic Journal of Combinatorics, 12, article R50, 2005.  http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50