Well, lets see how can it be implemented.

Step 1 – Turning a string to complex numbers
I used the Complex.java from Princeton.

Step 2 – Preparing the string to convolution
1. Get the numeric value of all chars in the string.
2. Flip the second (shorter) string.

Step 3 – Calculate searched string value

Step 4 – Convolve

Step 5 – Look for the value in the result

I still don’t know how will it work, but the idea is the following.
When we want to match string we need to perform operations which are very much like the convolution.
Of course convolution has the complexity of O(n^2) which is too much for string matching.

Well the idea is to use the FFT to convolve two strings and get the complexity of O(n log(n)).