Given two strings: s1, s2 s1 has some characters that equal to every character (call them universal characters) and s1 also has some characters that are not equal to any character.

find all occurences of s1 in s2.

for example

s1 = ab?a? s2 = aabcabaaa

here s1 occurs in s2 on indexes 1 (as abcab) and 4 (as abaaa)

i have tried using KPM or Z Array, but both failed do to unpredictable misbihaviour.

what algorithm can be used to solve this problem in linear time? (or at least O(n*logn))?