EDIT:
Sembra una ricerca di stringa Boyer-Moore modificata:
link
In pratica stai provando a dimostrare che l'abbinamento di S2 a diverse posizioni di S1 non funzionerà con nessun set di sostituzioni (o non funzionerà con i personaggi noti), il che ti permetterà di saltarle e andare avanti.
Nel tuo esempio specifico, sai che devi abbinare 5 caratteri. La stringa S1 ha 2 posizioni in cui potrebbe essere qualsiasi cosa, con 5 posizioni nel mezzo. Quindi, se riesci a far corrispondere i 4 caratteri a sinistra di S2 a qualcosa che non include una x in S1, o il 4 a destra, puoi testare solo l'ultimo carattere. (Neanche funziona qui.)
xadcdax
?cbaa
dcba?
Se avessi una stringa di 5 x "xxxxx" e tutti i caratteri in S2 in cui si trovano anche nell'elenco dei caratteri accettabili, allora hai una corrispondenza automatica.
xxxxx
?????
Per renderlo generico, puoi cercare tutte le occorrenze di x in S1, quindi provare a far corrispondere il lato sinistro o destro a S2, quindi compilare gli spazi vuoti, se necessario. Se avessi 2 occorrenze di x in una riga, avresti solo bisogno di cercare i 3 caratteri sinistro o destro di S2 (nel tuo caso specifico). Per cercare nel mezzo, finisci per far scorrere S2 attraverso la x trovata e tentando per abbinare a sinistra e destra.
??????x??????
dcba?
dcb?a
dc?aa
d?baa
?cbaa
????x??x???
dcba?
dcb?a
dc?aa
d?ba?
?cb?a
dc?aa
d?baa
?cbaa
Solo quando i personaggi in S1 sono specifici, allora devi fare delle sostituzioni.
Se tutti i caratteri nell'elenco di sostituzione sono in S2, non è necessario eseguire sostituzioni, la stringa corrisponde alla posizione.
Puoi saltare le posizioni di allineamento in cui S2 ha un carattere non presente nell'elenco di sostituzione che finisce su un personaggio degenerato.
Non ho alcun pseudo codice, quindi non sono sicuro del tempo di esecuzione.