Bail out on dead states for ShortestPrefix/ShortestSuffix

Seems we can stop traversing the given string once we get into a dead state