Shortest snippet

Cosmin Negruseri
11 iunie 2015

My friend George Nachman (googler and iTerm2 developer) ran into this problem recently:

Given a string pattern P and a large text file T, find the shortest substring of T that contains the the characters of P in the same order.

For example:
P = aab
T = abaccacbab
The shortest substring is acbab

How would you design an algorithm that works well in practice?

How does your solution change if P is guaranteed to have distinct characters.