s15.ps

c programming pearls answer

%!PS-Adobe-2.0
%%Copyright: Copyright (c) 1993 AT&T, All Rights Reserved
%%Version: 3.4
%%DocumentFonts: (atend)
%%Pages: (atend)
%%BoundingBox: (atend)
%%EndComments
/DpostDict 200 dict def
DpostDict begin
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 prologue for troff files.
%

/#copies 1 store
/Prologue (dpost.ps) def
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	addmetrics
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/landscapepage {
	landscape not {
		0 height scaling div neg translate	% not quite
		90 rotate
	} if
} bind def

/portraitpage {
	landscape {
		width scaling div 0 translate	% not quite
		-90 rotate
	} if
} bind def

/addmetrics {
	/Symbol /S null Sdefs cf
	/Times-Roman /S1 StandardEncoding dup length array copy S1defs cf
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newencoding exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall

	newencoding type /arraytype eq {newdict /Encoding newencoding put} if

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
end
%%EndProlog
%%BeginSetup
DpostDict begin
mark
/rotation 1 def
/gotpagebbox true def
/linewidth 0.5 def
/xoffset 0 def
/yoffset 0 def
/#copies 1 store
/magnification 1 def
%%FormsPerPage: 1
/formsperpage 1 def
%%Patch from lp
%%EndPatch from lp
/landscape false def
/resolution 720 def
setup
2 setdecoding
end
%%EndSetup
%%Page: 1 1
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
1 pagesetup
20 H f
(String Algorithms)1 1526 1 2117 960 t
(The Longest Duplicated String)3 2702 1 1080 1620 t
(Markov Text)1 1102 1 1080 1860 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-1)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 1 1
%%Page: 2 2
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
2 pagesetup
20 H f
(Longest Duplicated String)2 2300 1 1910 960 t
(The Problem)1 1148 1 720 1560 t
(Input: ``Ask not what your country can do for you,)9 4344 1 1008 2040 t
(but what you can do for your country''.)7 3394 1 1008 2280 t
(Output: `` can do for you'' \(15 chars\))7 3180 1 1008 2760 t
(A Simple Algorithm \(at least quadratic\))5 3422 1 720 3240 t
20 CW f
(maxlen = -1)2 1320 1 1296 3535 t
(for i = [0, n\))4 1680 1 1296 3770 t
(for j = \(i, n\))4 1680 1 1776 4005 t
(if \(l=comlen\(&c[i], &c[j]\)\))2 3240 1 2256 4240 t
(> maxlen)1 960 1 3216 4475 t
(maxlen = l)2 1200 1 2736 4710 t
(maxi = i)2 960 1 2736 4945 t
(maxj = j)2 960 1 2736 5180 t
20 H f
(An Important Function)2 1976 1 720 5720 t
20 CW f
(int comlen\(char *p, char *q\))4 3360 1 1296 6015 t
(i = 0)2 600 1 1776 6250 t
(while *p && \(*p++ == *q++\))5 3120 1 1776 6485 t
(i++)2256 6720 w
(return i)1 960 1 1776 6955 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-2)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 560 726
%%EndPage: 2 2
%%Page: 3 3
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
3 pagesetup
20 H f
(A Fast Algorithm)2 1482 1 2319 960 t
(Key Data Structures)2 1796 1 720 1560 t
20 CW f
(#define MAXN 5000000)2 2400 1 1296 1855 t
(char c[MAXN], *a[MAXN];)2 2760 1 1296 2090 t
20 H f
(Input ``Suf\256x Array'' for ``banana'':)4 2966 1 720 2630 t
20 CW f
(a[0]: banana)1 1440 1 1296 2925 t
(a[1]: anana)1 1320 1 1296 3160 t
(a[2]: nana)1 1200 1 1296 3395 t
(a[3]: ana)1 1080 1 1296 3630 t
(a[4]: na)1 960 1 1296 3865 t
(a[5]: a)1 840 1 1296 4100 t
20 H f
(The Sorted Suf\256x Array)3 2086 1 720 4640 t
20 CW f
(a[0]: a)1 840 1 1296 4935 t
(a[1]: ana)1 1080 1 1296 5170 t
(a[2]: anana)1 1320 1 1296 5405 t
(a[3]: banana)1 1440 1 1296 5640 t
(a[4]: na)1 960 1 1296 5875 t
(a[5]: nana)1 1200 1 1296 6110 t
20 H f
(Scan through to \256nd longest duplicated string)6 4022 1 720 6410 t
(\(``ana''\).)720 6650 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-3)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 3 3
%%Page: 4 4
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
4 pagesetup
20 H f
(The Suf\256x Array Code)3 1974 1 2073 960 t
(The Code \(usually about)3 2188 1 720 1560 t
20 HI f
(O)2964 1560 w
20 H f
(\()3136 1560 w
20 HI f
(n)3218 1560 w
20 H f
(log)3395 1560 w
20 HI f
(n)3728 1560 w
20 H f
(\)\))3856 1560 w
20 CW f
(while \(ch = getchar\(\)\) != EOF)5 3480 1 720 1855 t
(a[n] = &c[n])2 1440 1 1200 2090 t
(c[n++] = ch)2 1320 1 1200 2325 t
(c[n] = 0)2 960 1 720 2560 t
(qsort\(a, n, sizeof\(char *\), pstrcmp\))4 4320 1 720 2795 t
(for i = [0, n\))4 1680 1 720 3030 t
(if comlen\(a[i], a[i+1]\) > maxlen)4 3840 1 1200 3265 t
(maxlen = comlen\(a[i], a[i+1]\))3 3480 1 1680 3500 t
(maxi = i)2 960 1 1680 3735 t
(printf\("%.*s\\n", maxlen, a[maxi]\))2 3960 1 720 3970 t
20 H f
(4.8 secs on 807,503 characters of Homer's)6 3828 1 720 4510 t
20 HI f
(Iliad)4604 4510 w
20 H f
(:)4972 4510 w
(whose sake so many of the Achaeans have died)8 4312 1 1008 4990 t
( about at once)3 1276( Go)1 380(at Troy, far from their homes?)5 2642 3 1008 5230 t
(among the host, and speak fairly to them, man)8 4132 1 1008 5470 t
(by man, that they draw not their ships into the)9 4054 1 1008 5710 t
(sea.)1008 5950 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-15-4)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 4 4
%%Page: 5 5
%%PageBoundingBox: (atend)