book cover

Long Repeated Strings
(Illustrating Section 15.2 of
Programming Pearls)

Section 15.2 describes long repeated strings in text and gives an example. Here are some more examples, generated by this program from several sources.

King James Bible

Verse Numbers Included

the house of his precious things, the silver, and the gold, and the spices, and the precious ointment, and all the house of his armour, and all that was found in his treasures: there was nothing in his house, nor in all his dominion, that Hezekiah shewed them not.

This text is found in 2 Kings 20:13 and in Isaiah 39:2. Each text line in the original file begins with the chapter and verse (i.e., ``GEN 1:1 In the beginning God created ...''). Long repeated strings therefore could not cross verse boundaries; the next experiment deleted those identifiers.

Verse Numbers Excluded

, offered: His offering was one silver charger, the weight whereof was an hundred and thirty shekels, one silver bowl of seventy shekels, after the shekel of the sanctuary; both of them full of fine flour mingled with oil for a meat offering: One golden spoon of ten shekels, full of incense: One young bullock, one ram, one lamb of the first year, for a burnt offering: One kid of the goats for a sin offering: And for a sacrifice of peace offerings, two oxen, five rams, five he goats, five lambs of the first year: this was the offering of Ahi

Numbers 7 describes offerings made over a period of twelve days; much of this string appears twelve times.

Longest String That Occurs Twelve Times

, full of incense: One young bullock, one ram, one lamb of the first year, for a burnt offering: One kid of the goats for a sin offering: And for a sacrifice of peace offerings, two oxen, five rams, five he goats, five lambs of the first year: this was the offering of

This string occurs twelve times in Numbers 7. This string was computed using the method of Solution 15.8.

Programming Pearls

The Entire Text

6, 8, 12, 17-18, 51-55, 59, 62, 70-72, 82, 87-98, 116, 119, 121, 128, 137, 162, 164, 187-189, 206, 210, 214, 221, 230

I was surprised to find that the longest repeated string in the book was in the index. The same sequence of numbers are repeated for the entries for ``experiments'', ``run time'' and ``time, run''.

Index Excluded

expression is costly, replace it by an algebraically equivalent expression that is cheaper to evaluate. I

This text appears in both the Logic Rules and the Expression Rules of Appendix 4: Rules for Code Tuning.

The Iliad

The Entire Text

whose sake so many of the Achaeans have died at Troy, far from their homes? Go about at once among the host, and speak fairly to them, man by man, that they draw not their ships into the sea.

This example (on Samuel Butler's translation of Homer's Iliad) was used in Section 15.2. describes long repeated strings in text and gives The text first occurs when Juno suggests it to Minerva as an argument that might keep the Greeks (Achaeans) from departing from Troy; it occurs shortly thereafter when Minerva repeats the argument verbatim to Ulysses.

Copyright © 1999 Lucent Technologies. All rights reserved. Mon 6 Nov 2000