Once the suffix array is constructed, the short routine shown in Figure 12.50 can be invoked from
Question:
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.
Figure 12.50 LCP array construction from suffix array
Transcribed Image Text:
* Create the LCP array from the suffix array * @param s the input array populated from 0..N-1, with available pos N * @param sa the already-computed suffix array 0..N-1 * @param LCP the resulting LCP array 0..N-1 */ public static void makeLCPArray ( int [] s, int [ ] sa, int [] LCP ) int N = sa.length; int [] rank = new int[ N ]; 10 11 s[ N] = -1; 12 for( int i = 0; i < N; i+ ) rank[ sa[ i]] = i; 13 %3D 14 15 int h = 0; for( int i = 0; i < N; i++ ) if( rank[ 1] > 0 ) 16 17 18 { 19 int j = sa[ rank[ i] - 1 ]; 20 21 while( s[ i +h ] == s[ j + h] ) 22 %3D 23 htt; 24 LCP[ rank[ i]] = h; if( h > 0 ) 25 26 27 h--; 28 29
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 75% (4 reviews)
a We see that for all i ranksai i Thus rank and sa are inverses of each other The sa array gives the list of suffixes in alphabetical order In other w...View the full answer
Answered By
Joseph Mwaura
I have been teaching college students in various subjects for 9 years now. Besides, I have been tutoring online with several tutoring companies from 2010 to date. The 9 years of experience as a tutor has enabled me to develop multiple tutoring skills and see thousands of students excel in their education and in life after school which gives me much pleasure. I have assisted students in essay writing and in doing academic research and this has helped me be well versed with the various writing styles such as APA, MLA, Chicago/ Turabian, Harvard. I am always ready to handle work at any hour and in any way as students specify. In my tutoring journey, excellence has always been my guiding standard.
4.00+
1+ Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Question Posted:
Students also viewed these Computer Sciences questions
-
Draw a suffix tree and show the suffix array and LCP array for the following input strings: a. ABCABCABC b. MISSISSIPPI
-
A system of the form shown in Figure 12.1 has where 3 p 5,0 q 1, and 1 r 2. we will use a compensator with all real poles and zeros. Select an appropriate compensator to achieve robust...
-
A Latin square is an n-by-n array filled with n different Latin letters, each occurring exactly once in each row and once in each column. Write a program that prompts the user to enter the number n...
-
Identify an accurate sentence about parenting in the United States. a. Fathers of toddlers play more roughly with daughters than with sons. b. During the first year, fathers treat boys and girls as...
-
A 90.0-kg fullback running east with a speed of 5.00 m/s is tackled by a 95.0-kg opponent running north with a speed of 3.00 m/s. If the collision is perfectly inelastic, (a) Calculate the speed and...
-
A virus that causes an initial infection and then later becomes dormant is called a__________ virus.
-
The equilibrium constant for the reaction \(\mathrm{N}_{2}(\mathrm{~g})+3 \mathrm{H}_{2}(\mathrm{~g}) ightarrow 2 \mathrm{NH}_{3}\) is 0.1084 . Under the same conditions, the equilibrium constant for...
-
During the fourth quarter of 2013, there were seven biweekly paydays on Friday (October 4, 18; November 1, 15, 29; December 13, 27) for Clarke's Roofing. Using the forms supplied on pages 4-58 to...
-
Journalize the input settings presented. As of August 31, the following information was accumulated to prepare the adjustment entries for the Casa de Papel company: The balance for the materials...
-
X Ltd. has 10 lakhs equity shares outstanding at the beginning of the accounting year 2016. The appropriate P/E ratio for the industry in which D Ltd. is 8.35. The earnings per share is Rs. 15 in the...
-
Show that every AVL tree can be colored as a red-black tree. Are all red-black trees AVL?
-
The government market is obviously an extremely large one, yet it is often slighted or even ignored by many firms. Red tape is certainly one reason, but there are others. Discuss the situ a tion and...
-
Bon Secour Medical Group borrowed $600,000 on July 1, 2014, by issuing a 14% long term note payable that must be paid in three equal annual installments plus interest each July 1 for the next three...
-
Look at this partial class definition, and then follow the subsequent instructions: a. Write a constructor for this class. The constructor should accept an argument for each of the fields. b. Write...
-
One of the GLOBE Project teams nine cultural variables is future orientation, which refers to the level of importance a society attaches to future-oriented behaviors, such as planning and investing...
-
On Wednesday, November 21, the WeChat account of the official Peoples Daily issued a statement believed to be from the Ministry of Culture and Tourism; the Dolce & Gabbana (D&G) fashion show in...
-
Refer to the facts in Tax Form/Return Preparation Problem C:9-58. Now assume the company is an S corporation rather than a partnership. Additional facts are as follows: Drs. Bailey and Firth formed...
-
In pairs, imagine that you are buyers from one country and sellers from another. Your colleague says that it is not necessary to spend time and effort studying the selling-country culture before the...
-
Maybepay Life Insurance Co. is selling a perpetual annuity contract that pays $3,100 monthly. The contract currently sells for $325,000. What is the monthly return on this investment vehicle? What is...
-
The Pletcher Transportation Company uses a responsibility reporting system to measure the performance of its three investment centers: Planes, Taxis, and Limos. Segment performance is measured using...
-
Compare the shadow-paging recovery scheme with the log-based recovery schemes in terms of ease of implementation and overhead cost.
-
Consider a database consisting of 10 consecutive disk blocks (block 1, block 2, . . ., block 10). Show the buffer state and a possible physical ordering of the blocks after the following updates,...
-
Explain how the buffer manager may cause the database to become inconsistent if some log records pertaining to a block are not output to stable storage before the block is output to disk.
-
Compare and contrast different deadlock prevention techniques such as resource ordering, the "hold and wait" condition, and preemptive resource allocation. Which methods are most effective for...
-
The following information is taken from Aden Company's records: Product Group Units Cost/Unit Market/Unit A 1 700 $1.10 $0.90 B 1 250 1.50 1.55 C 2 150 4.90 5.15 D 2 100 6.50 6.40 E 3 80 25.00 24.60...
-
American Food Services, Incorporated leased a packaging machine from Barton and Barton Corporation. Barton and Barton completed construction of the machine on January 1, 2024. The lease agreement for...
Study smarter with the SolutionInn App