The machine SPOJ used is ~0.75 GHz. So these two problems need DFA with heavy constant optimization in order to get Accepted. Hashing can not work because it has a very large constant (divide & modulus are too slow) and its time complexity is O(nlogn) not O(n).
There are some problems with these constraints, like KPARCH (you can see it in my TODO list), my algorithm is O(nlognlogn) and gets TLE. Someone who got Accepted told be that an algorithm with time complexity O(nlogn) can AC.