We need to find all the positions where the pattern starts in the text.

So from the position where it ends we need to compute the position where it starts,

and to do that we need to subtract length of the pattern -1,

but that would be the position in S.

And to compute the position in the text,

we also need to subtract the length of the pattern and one for the dollar.

So in total, we need to subtract two length of the pattern from the position in

the string S to find the starting position of the pattern in the initial text.

And there is another place where prefix function of string big S

is equal to the length of the pattern.

And again, there is an occurrence of the pattern ending in that position.

And why does algorithm even works?

First, we need to notice that the prefix function for

this string big S is always less than or equal to the length of the pattern.

Because of the dollar sign it occurs right after the end of the pattern so

when the border is bigger,

we would need to have another occurrence of dollar in the string big S.

But dollar is only between pattern on the text and is absent from the text.

So prefix function cannot be bigger in under the life of the pattern.