There are couple string match algorithms which can achieve linear time to do the search in stead of O(n*m). Suffix tree algorithm requires to pre-compute the suffix tree and requires O(K*N) space, K is the alphabet size and N is the maximum length of the strings. KPM also needs to pre-compute a table of failure function to quickly find the next starting positions in two string. Rabin Karp algorithm is probably the simplest one, which use hash to compare two strings.
The key to Rabin Karp algorithm is to compute the hash effectively and quickly. This is done by dynamic programming, which is current substring hash value is computed based on the previous one.
Here is the Rabin Karp algorithm to solve an online algorithm for palindrome checking.
Thanks to Peng Li for bringing up this problem. Here is the link to his page on this: http://allenlipeng47.com/PersonalPage/index/view/157/nkey
your code has no difference with the on in g4g(http://www.geeksforgeeks.org/online-algorithm-for-checking-palindrome-in-a-stream/).
ReplyDeleteMy code adds a function for queue. It can help queue be able to compute hashcode in O(1) time when enQueue or deQueue happens. You remember we wrote the code to monitor max/min value in queue? I think this can make queue much powerful.
this code is slightly different that in stead of compute first/second half, it compute forward/backward.
Deletedo we need deQueue op?