We'll use a window of size |S| to traverse B. We have an instance of S in B when the frequency of letters in our window is the same as the frequency of letters in S (we just rearrange the letters to get S, which means we indeed have a permutation).

For now we have an O(Σ * |B|) algorithm if you pass all the elements of the frequency vector every time the window gets update (I will leave as an exercise for you to try to make it O(Σ + |B|)).

As a final observation, if we only need to count the number of occurrences the complexity is equal to the above, though if we have to print all strings observe that we might have a total of O(|S|²) characters in the worst case (consider a case S = "aa...a", B = "aa....a" where the size of B is the double of A)

If S is small like you say then one possible approach is to assign each letter of the alphabet to a prime number, for example: 'a' = 2, 'b' = 3, 'c' = 5, 'd' = 7, .... Then calculate a number for the value of s by multiplying all the values together. For example, for s = "ab", the value is "2*3=6". Now any sub string of b will be a permutation of s if and only if its value is 6 (This follows from the prime factorization theorem). You can calculate this "value" in a rolling basis for an algorithm to run in O(|b|)

Last note: s must be small or you'll overflow the value.

Running example: s="ab" so value we want is 2 * 3 = 6.

Current window in b is ["ba"], value1 = 3*2=6. value1=required value so output "ba"

Current window in b is ["ab"], value2 = value1/3 * 3 = 6 = required value so output "ab"

Current window in b is ["bb"], value3 = value2/2 * 3 = 9 =/= required value

Current window in b is ["ba"], value4 = value3/3 * 2 = 6 = required value so output "ba"

This is a very similar approach to the Rabin Karp hashing function, only difference is that one searches for exact matches, this "hashing" function searches only for permutations.