An Introduction To String Algorithms – Carl Kingsford (1)

They have the nice property that, asymptotically, they take linear space in the string they contain. The suffix tree of T takes space O(|T|), but the big-O notation hides a lot of overhead: we have to maintain node structures, with pointers to encode the edges, plus some numbers on each edge. When dealing with really large strings, even a factor of 10 bigger than T could be a significant problem.

That raises the question whether we can get a lot of the benefits of suffix trees without all that overhead. That is the goal of suffix arrays [Manber and Myers, 1990, 1993]. 16.1 Suffix tree operations in less space Imagine that you write down all the suffixes of a string T of length t. The ith suffix is the one that begins at position i.

Now imagine that you sort all these suffixes and then write down the starting position of each suffix in an array in their sorted order. This is the suffix array. For example, suppose T = “banana$”, and we’ve sorted the suffixes: 6 $ 5 a$ 3 ana$ 1 anana$ 0 banana$ 4 na$ 2 nana$ . (16.1) The numbers to the left are the indices of these suffixes.

The suffix array is the array of these numbers. (16.2) This array can be computed in a straightforward way by sorting the suffixes directly. This takes O(t2 log t) time because each comparison of two suffixes takes O(t) time. In fact, the suffix array can be constructed in O(t) time, which we will see in Chapter 17. 16.2 Suffix array ↔suffix tree Definition 16.1 (Suffix Array). The suffix array SA(S) of a string S is a permutation of the integers {0, . . .

, |S| −1}, where SA(S)[i] is the starting position of the alphabetically ith suf- fix. That is, if we sort all the suffixes of S, SA(S)[i] is the starting location of the suffix that occurs at position i in that sorted list. ■ It’s often handy to have an auxiliary array called the “LCP” array around. Each successive suffix in this order matches the previous one in some number of letters.

(Maybe zero letters.) This is recorded in the longest common prefix array, or the LCP array.

Copyright © 2026 Carl Kingsford Princeton University Press is committed to the protection of copyright and the intellectual property our authors entrust to us. Copyright promotes the progress and integrity of knowledge created by humans. By engaging with an authorized copy of this work, you are supporting creators and the global exchange of ideas. As this work is protected by copyright, any reproduction or distribution of it in any form for any purpose requires permission; permission requests should be sent to [email protected]. Ingestion of any IP for any AI purposes is strictly prohibited.

Published by Princeton University Press 41 William Street, Princeton, New Jersey 08540 99 Banbury Road, Oxford OX2 6JX press.princeton.edu GPSR Authorized Representative: Easy Access System Europe – Mustamäe tee 50, 10621 Tallinn, Estonia, [email protected] All Rights Reserved ISBN 9780691274539 ISBN (e-book) 9780691274546 Library of Congress Control Number: 2025948270 British Library Cataloging-in-Publication Data is available Editorial: Hallie Stebbins and Chloe Coy Production Editorial: Mark Bellis Text and Jacket Design: Wanda España Production: Erin Suydam Publicity: William Pagdatoon Copyeditor: Lor Campbell Gehret This book has been composed in Minion Pro Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 To Jessica, Henry, and Teddy Contents Preface xvii 1 Introduction 1 1.1 What are strings?

1 1.2 Why study string algorithms? 1 1.3 What are our goals?

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 7647c9e898e065aa
• File Extension: .pdf
• File Size: 12,195,600 bytes (11.631 MB)
• Title: –
• Author: Unknown
• ISBN: 9780691274539, 9780691274546
• Pages: 378
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 634.25 minutes
• Total Words: 126,849
• Total Characters: 687,769
• Average Words per Page: 335.58
• Average Characters per Page: 1819.49

Most Frequent Words

string (709), algorithm (659), suffix (497), time (453), strings (382), node (336), tree (321), log (308), character (297), length (278), alignment (277), one (270), number (269), since (260), two (257), problem (249), using (246), set (227), array (225), characters (225), between (220), first (219), use (209), let (193), case (192), compute (188), values (185), edge (183), find (180), prefix (172), bwt (169), gap (168), also (168), path (168), nodes (167), start (166), position (163), every (161), bits (160), space (159), given (159), algorithms (156), edit (154), example (154), function (153), see (153), match (151), cost (149), chapter (148), edges (147), state (146), graph (145), need (143), new (142), sequence (135), following (134), optimal (132), row (131), distance (129), used (128), definition (123), probability (122), bit (122), notes (121), pattern (121), order (120), exercises (118), substring (115), search (114), trees (114), end (113), takes (113), now (111), rank (110), data (109), matrix (109), give (108), starting (105), next (104), many (103), block (103), matching (102), proof (101), graphs (101), computing (100), total (99), want (99), possible (98), store (96), theorem (95), value (95), alphabet (94), last (94), running (93), sequences (92), output (92), input (92), longest (91), suffixes (91), regular (90).

PDF Download