Würde da nicht auch ein pos bzw. posex reichen?
Ich denke nicht
Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3
Mein gedanklicher Ansatz wäre: Schreibe die beiden Zeichenketten untereinander und verbinde die gleichen Zeichen zwischen den Wortern mit einer geraden Linie. Alle Linien (bzw. deren Zeichen) die sich mit keiner anderen kreuzen sind auf jeden Fall im längsten Muster.
Nun wäre die Frage, ob es eine gute Strategie gibt, um kreuzende Linien zu entfernen oder ob man da "dummes" Brute-Force machen muss.
EDIT/PS: Die Idee ist hier: Die kreuzenden Linien zeigen wo Zeichen in beiden Wörtern in unterschiedlicher Reihenfolge vorkommen.