Online validation of the pi and pi' failure functions

Details Online validation of the pi and pi' failure functions Online validation of the pi and pi' failure functions

2009-01-19

arxiv.org/abs/0901.2897v2

Computer Science

Data Structures and Algorithms

submitted

Scientific paper

Let pi_w denote the failure function of the Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A[1..n], is there a word w over arbitrary alphabet such that A[i]=pi_w[i] for all i? Moreover, what is the minimum required cardinality of the alphabet? We give a real time linear algorithm for this problem in the unit-cost RAM model with \Theta(log n) bits word size. Our algorithm returns a word w over minimal alphabet such that pi_w = A as well and uses just o(n) words of memory. Then we consider function pi' instead of pi and give an online O(n log n) algorithm for this case. This is the first polynomial algorithm for online version of this problem.

Affiliated with

Also associated with

No associations

Rating

Online validation of the pi and pi' failure functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online validation of the pi and pi' failure functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online validation of the pi and pi' failure functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-434268