Modify the algorithm of Fig. 3.19 to compute the failure function for general tries. Hint : The...

Modify the algorithm of Fig. 3.19 to compute the failure function for general tries. Hint : The ma jor di erence is that we cannot simply test for equality or inequality of bs+1 and bt+1 in lines (4) and (5) of Fig. 3.19. Rather, from any state there may be several transitions out on several characters, as there are transitions on both e and i from state 1 in Fig. 3.21. Any of those transitions could lead to a state that represents the longest suffix that is also a preix.