Once the suffix array is constructed, the short routine shown in Figure 12.50 canbe

Chapter 12, Problem 12.9

(choose chapter or problem)

Once the suffix array is constructed, the short routine shown in Figure 12.50 canbe invoked from Figure 12.32 to create the longest common prefix array.a. In the code, what does rank[i] represent?b. Suppose that LCP[rank[i] ] = h. Show that LCP[rank[i+1] ] h 1.c. Show that the algorithm in Figure 12.50 correctly computes the LCP array.d. Prove that the algorithm in Figure 12.50 runs in linear time.1 /*2 * Create the LCP array from the suffix array3 * @param s the input array populated from 0..N-1, with available pos N4 * @param sa the already-computed suffix array 0..N-15 * @param LCP the resulting LCP array 0..N-16 */7 public static void makeLCPArray( int [ ] s, int [ ] sa, int [ ] LCP )8 {9 int N = sa.length;10 int [ ] rank = new int[ N ];1112 s[ N ] = -1;13 for( int i = 0; i < N; i++ )14 rank[ sa[ i ] ] = i;1516 int h = 0;17 for( int i = 0; i < N; i++ )18 if( rank[ i ]>0)19 {20 int j = sa[ rank[ i ] - 1 ];2122 while( s[ i + h ] == s[ j + h ] )23 h++;2425 LCP[ rank[ i ] ] = h;26 if( h > 0 )27 h--;28 }29 }Figure 12.50 LCP array construction from suffix array