ࡱ> @=y {K V x5x5xTMHQ=G4CMf"DM (kfDD_nfhgpۦ)R6yO~ zw{Ͻ{{H(sJxA}=3q1zʁ;}f|.Ft,. ;p }.p%/hN:4 _G:8$zv3L+EBPʞ?74{7|VP u@hA/:JJH3!%ƊYyXflB-c<Hs,39Ef28%E #%$EEI+ڼ&}LĵZTzHYhwWW6WīW?wr[|gRs w4s '8V!"MvTSgdψ߲Y` .aH0'!E7Jك1 GͧKb b1wy1F8.VaYQgݺ|=;^p=,`0s-d!%}Fx)-_ή\+\'*͒ (    0  VISIO Visio.Drawing.60.Microsoft Visio DrawingZ/ 0DTimes New Roman0  0DWP MathA Roman0  0$  @n?" dd@  @@``  !  6    >j:4/  O$$$"$y {K V  0e0e     A@ A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| 3f3f3@ g4LdLd0t *ppp@ <4!d!dDt <4BdBdD? %'Sorting suffixes of two-pattern strings (tF. Franek & W.F. Smyth Algorithms Research Group Computing and Software McMaster University Hamilton, Ontario Canada0uE u           ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> (    6d! P  B Click to edit Master title style!  0!   RClick to edit Master text styles Second level Third level Fourth level Fifth level!      0$" ``  Y*  0" `   [*  0" `   [*H  0޽h ? ̙33v &0(  l  C Y  l  C ZpP     0dZ @@ w3PSC04, Praha, Czech Republic, August-September 200444 4  0Z  p WSlide 1" H  0޽h ? ̙33" @ V(   _  0[P` cIn 2003 several very different linear-time (recursive) algorithms to sort suffixes of strings appeared. All work in four basic steps: . Split all suffixes into two sets . Sort the first set of suffixes by recursion (recursive reduction of the problem) . Sort the second set of suffixes based on the order of the first set . Merge both sorted sets togethern 2# 12S 22F 32" 42d  d  0[ o WSlide 2" H  0޽h ? ̙33- P ](  f  0] Our question --- will two-pattern strings exhibit a  natural tendency to reduce the problem in a recursive fashion? Two-pattern strings were introduced by us as a generalization of Sturmian (and hence Fibonacci) strings. Let p, q be binary strings.  = [p,q,i,j] is an expansion of scope  if |p|, |q| d"  and i `" j non-negative integers. We require p and q to be dissimilar enough to be efficiently recognizable (see the paper for the details).X 2 c 3n                      #    X     0d] o WSlide 3" H  0޽h ? ̙33I `5(   # 0D\0} < 2   3 0] o WSlide 4"  5 0$^  (a)=piq, (b)=pjq, (x[1..n])=(x[1])(x[2..n]) 1%2(x)=1(2(x)) x is two-pattern string of scope  iff there is a sequence 1, 2,...,n of expansions of scope  so that x=1%2% & %n(a) The "nice" properties of two-pattern strings (see a series of papers by Franek, Smyth and others): can be recognized in linear time$ 2" 2                            $     $$3 $3 3 $  $  $  $ $$$     $  $$e$"  FH  0޽h ? ̙33 php(    0^ o WSlide 5"    0D_`3 a when recognized, the canonical expansion sequence is computed repetitions and near repetitions can be effectively computed in linear time using recursive approach generalize finite fragments of the Fibonacci string and Sturmian strings can easily be generated and represented in recursive fashion exhibit rich yet comprehensible recursive structureb 2b  bH  0޽h ? ̙33 1)( RD   0\ o WSlide 6"   0$a` ~6 they occur relatively frequently among binary strings7 27  7  0a3` :An illustration of a very simple two-pattern string; will be used later to illustrate the workings of the algorithm: [a,b,2,3] apply to a: a ! aab [ba,ab,1,2] apply to aab: aab ! baab baab babaab baabbaabbabaab is a two-pattern string of scope 2 2v        3  3        3  3  $  H  0޽h ? ̙33q ! (     0a o WSlide 7"   0Db3P ZNow we can rephrase our question: Given an expansion  and knowing the order of suffixes of a two-pattern string x, can we efficiently determine the order of suffixes of (x)? The answer is yes and in the following we describe the algorithm. So let x be a two-pattern string of scope  and let  = [p,q,i,j] be an expansion and let y = (x). Let 1 < 2 < & < |x| the sorted suffixes of x. We are assuming that q  p (since then x1 < x2 iff (x1) < (x2), otherwise we work with ^ 2" O  :   I  1                            $               H  0޽h ? ̙333 $0 _( 0 $ Q$ 0b o WSlide 8" T R$ 0c3 complements and reverse the resulting order of suffixes while taking complements of the suffixes). First we assign all suffixes of y into various buckets:, 2    | S$ T?@ ` p | V$ T?@  | Y$ T?@ 0 v [$ N?@  v \$ N?@  v ]$ N?@   v ^$ N?@ p v _$ N?@ v a$ N?@   v b$ N?@ @ v c$ N?@ @`  f$ Tdc ?P ,  N& & & .(2$  g$ 0c3 G  xA,k = {pkq() :  is a proper suffix of x or =}  is a suffix of p and 0 < k < iW 2$ $             Wp z$ H?@    {$ 0d3p0  * pk q ()F 2       B |$  `D? B }$  `D? @B ~$  `D? P B $  `D?P ~8    $   $ S d0e0e    B0CDE(F A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      $B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     F    $  P` `  $ c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      $B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     H $ 0޽h ? ̙33# /#'#%)"( ` ( _) 0d o WSlide 9" .8 P` p  z) Pp ~ m) N?P ~ n) N? P  ~ o) N?`P p x p) H?P  x q) H? P @ x r) H?@P ` x s) H? P x t) H? P x u) H?@P ` x v) H?`P  x w) H?P   x) NDe ?P` l  N& & & .(2$ x y) H?P `  ) 03g nA,i = {piq() :  is a proper suffix of x or =}  is a suffix of p and also a suffix of q or A,i = {piq() : b proper suffix of x,  can be }  is a suffix of p and not a suffix of ql 2$ $ $$          +  $ $ $$              F    )  @p  ) c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      )B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     |8 P p$  )0 Pp  ) T?  ) T?   ) T?` p ~ ) N?  ~ ) N?  @ ~ ) N?@ ` ~ ) N? ~ ) N? ~ ) N?@ ` ~ ) N?`  ~ ) N?   ) T ?P l$  N& & & .(2$ ~ ) N? F    )  P p ) c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      )B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     H ( 0޽h ? ̙33j/ //0,.(  , , 04n o XSlide 10"  v , N?0 @ @v , N? @v , N?@p , H?@p , H?@p , H?@p , H?@ ` @p , H?` @p , H?@p , H?@p , H?0 @ , Nn ? N& & & .(2$  , 0n3   A,k = {pkq() : b proper suffix of x,  can be }  is a suffix of p and i < k < jY 2 $ $                 Yp , H?`@ , 0o3 ] * pk q ()F 2       B ,  `D?p`B ,  `D?` B ,  `D?0 PB ,  `D? F    , p  , c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      ,B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     F    , p 0  , c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      ,B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     v , N?  v , N? P ` v , N?  p , H? ` p , H?  p , H?  p , H?  0 p , H? 0 P p , H?  p , H?  p , H?   , Np ? d  N& & & .(2$ p , H? p  , 0p30  " q (): 2      B ,  `D?P `B ,  `D?P ` `B ,  `D? F    ,  @ p , c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      ,B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      , 04q30   v B = {q() :  proper nontrivial suffix of x}  is a suffix of p and i < k < jS 2 $ $  %          SH , 0޽h ? ̙337 f7^7 406(  0 0 0d$  XSlide 11"  v 0 N?  v 0 N?P `v 0 N?p 0 H?`p 0 H?p 0 H?p 0 H? 0 p 0 H?0 P p 0 H?p 0 H?p 0 H?  0 N$ ?$ N& & & .(2$ p 0 H?    0 0%3 P 4 pi q ()^ 2          B 0  `D? B 0  `D?` B 0  `D?pPF    0 @00 0 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0 0%3  C = {piq() : a proper suffix of x,  can be }  is a suffix of q but not of pV 2 $ $              VB 0  `D?@ F    0  P p 0 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     v 0 N?`  v 0 N?` P ` v 0 N?`  p 0 H?` ` p 0 H?`  p 0 H?`  p 0 H?`  0 p 0 H?` 0 P p 0 H?`  p 0 H?`  p 0 H?`   0 ND& ?p   N& & & .(2$ p 0 H?`    0 0'3Pm 4 pj q ()^ 2          B 0  `D? pB 0  `D? ` B 0  `D?pp0F    0    0 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0 0d'3  f D = {pjq() : b proper suffix of x,  can be }  is a suffix of qI 2 $ $$            IB 0  `D? `F    0    0 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      0B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     H 0 0޽h ? ̙33n" ""&4!(  4 4 01  XSlide 12"  H 4 03 X E = {:  is a nontrivial suffix of p or q}b- 2 $#       -v 4 N?0 v 4 N?00 @v 4 N?0p 4 H?0@`p 4 H?0`p 4 H?0p 4 H?0  p 4 H?0 0 p 4 H?0p 4 H?0p 4 H?0 4 N ?@ N& & & .(2$  4 03p  F 2  B 4  `D?`F    4 P 4 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      4B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @     v 4 N?@P v 4 N? v 4 N?p 4 H?p 4 H?p 4 H?p 4 H?P p p 4 H?p p 4 H?p 4 H? p 4 H? @ 4 N4 ? $ N& & & .(2$ B 4  `D? P F    4 @ 4 c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      4B c j0e0e    B0CDE(F @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @<x`@0 @      4 0T3 p-  F 2   4 0t3 ` : All suffixes are covered by A-E ! Order of suffixes in buckets A-D determined by  ! A-D buckets are order invariant !{ 2{  {H 4 0޽h ? ̙33t $<( w < < 0Ԛ  XSlide 13"   < 03b \So, if we can determine the order of buckets, we can determine the order of all suffixes in buckets A-D. To merge in the suffixes from E is easy (brute force only requires d" 42|y| steps). The main results is based on the fact that the order of buckets A-D can be efficiently determined using 5 cases: (C1) 1  2 (C2) 2  1 (C3) 1 is a proper prefix of 2 (C4) 2 is a proper prefix of 1 (C5) 1=2=  2                                   H < 0޽h ? ̙33  D < @ ( w @ @ 0  XSlide 14"   @ 0T3` |(C1) A1,k1n A2,k2 (C2) A2,k2n A1,k1 (C3) 2=1 (a) if   p, then A2,k2n A1,k1 (b) otherwise A1,k1n A2,k2 (C4) 1=2 (a) if   p, then A1,k1n A2,k2 (b) otherwise A2,k2n A1,k1 (C5) (a) if k1 < k2, then A,k1n A,k2 (b) if k1 = k2, then A,k1=A,k2 (c) if k1 > k2, then A,k2n A,k1^ 2 $ $ $ $ $($ $ $ $ $ $ $ $ $ $($ $ $ $ $         $ $ $ $ $($ $ $ $ $ $ $ $ $ $($ $ $ $ $        $ $ $ $ $($ $ $ $ $ $ $ $ $ $($ $ $ $ $      $ $ $($ $ $     $ $ $ $ $ $     $ $ $($ $ $ ^H @ 0޽h ? ̙33  DP(  D D 0D  XSlide 15"  . D 0 3`  (C1) A1,k n B2 (C2) B2 n A1,k (C3) 2=1 (a) if   p, then B2 n A1,k (b) otherwise A1,k n B2 (C4) 1=2 (a) if pkq  pq, then A1,k n B2 (b) otherwise B2 n A1,k (C5) B n A,k 2 $ $ $ $($ $ $ $ $ $($ $ $ $          $ $ $($ $ $ $ $ $ $ $ $ $($ $ $            $ $ $ $ $($ $ $ $ $ $ $($ $ $ $ $ $ $($ $ $ " D 0@ bNo bucket comparison requires more than 3 steps.22 2)    2H D 0޽h ? ̙33 HV(  H H 0d  XSlide 16"  ^ H 0$ 3` ,Similarly A~C, A~D, B~B, B~C, B~D, C~C, and C~D. One more example: (C1) B1 n B2 (C2) B2 n B1 (C3) 2=1 (a) if qp  qp, then B2 n B1 (b) otherwise B1 n B2 (C4) 1=2 (a) if qp  qp, then B1 n B2 (b) otherwise B2 n B1 (C5) B1 =B2 2C  $ $ $ $($ $ $ $ $ $($ $ $            $ $ $($ $ $ $ $ $($ $ $          $ $ $($ $ $ $ $ $ $($ $ $ $ $ $ $ $ $ $ $ H H 0޽h ? ̙33 0( L( Q L L 0đ hThe High-level logic of the algorithm: . Create names (A,) for every suffix  of p. (This requires at most  steps. Each name will be eventually replaced by a sequence of buckets.) . Sort the names according to the comparisons of the four A buckets (according to (C1)-(C4)). (This requires at most 23 steps as we are sorting  names and each comparison requires at most 2 steps.) . Replace every name (A,) by a sequence of names (A,,k), 0< k < j. Let us call the resultingx' 2 12 22` 32T      F  `       ,    D     L 0  XSlide 17"  H L 0޽h ? ̙33x ( 0iP( "i P gP 0tL  XSlide 18"   iP 0d%P  `BUCKETS. (Now we have the names of A buckets in the proper order. This requires at most |y| steps as the size of BUCKETS is d" |y|.) . Create names (B,) for every suffix  of p. (This requires at most  steps.) . Merge into BUCKETS all names (B,) according to comparisons. (This requires at most |BUCKETS|32 steps, as we are merging in  names and each comparison requires d" 3 steps)"R45     2           .        A         #      H P 0޽h ? ̙33 ~@9T( ȃK  T 7T 0&  XSlide 19"   9T 0$a V. Create names (C,) for every suffix  of q that is not a suffix of p. (This requires at most 2 steps.) . Merge into BUCKETS all names (C,) according to comparisons. (This requires at most |BUCKETS|32 steps.) . Create names (D,) for every suffix  of q. (This requires at most  steps.) . Merge into BUCKETS all names(D,) according to comparisons. (Now we have all required bucket names, except E, in proper order.:l6m7Q89,           A         -        @  -        H T 0޽h ? ̙33 RJPX(  X X 0  XSlide 20"   X 0  TThis requires at most |BUCKETS|32 steps.) 0. Traverse BUCKETS and replace each name by a sequence of suffixes according to the sequence of suffixes of x. Let us call this sequence SUFFIXES. (Now we have all suffixes from buckets A-D in proper order. This requires at most |y| steps.) 1. Merge into SUFFIXES the suffixes from the bucket E. (This requires at most |y|42 steps.) Done in less than (23+142+3+2)|y| steps!,1       p  &  P      :                   H X 0޽h ? ̙33 2*`\(  \  \ \ 0  XSlide 21"  , \ 0$ The algorithm works in 2(23+142+3+2)n steps, where n is the size of the input string. An example: x = aab$ y = baabbaabb a b a a b $ =[ba,ab,1,2] ordered suffixes of x: 1 2 3 ordered suffixes of y: 12 2 6 13 10 3 7 14 11 1 5 9 4 8        #                       -    \ 0D!pw W1 2 3"   \ 0'p  w'1 2 3 4 5 6 7 8 9 10 11 12 13 14"('  (H \ 0޽h ? ̙33  t l p` (  ` ` 0  XSlide 22"   ` 03x Aba,1 = {babaab() : b proper suffix of x,  can be }= {babaab}={9} Aa,1 = {abaab() : b proper suffix of x,  can be }= {abaab}={10} Bba = {baab() :  proper suffix of x}={baab(ab), baab(b)}={baabbaabbabaab, baabbabaab}={1,5} Ba = {aab() :  proper suffix of x}={aab(ab), aab(b)}={aabbaabbabaab, aabbabaab}={2,6} Cab = {abbaab() : a proper suffix of x}= {abbaab(b)}={abbaabbabaab}={3} Cb = {bbaab() : b proper suffix of x}= {bbaab(b)}={bbaabbabaab}={4} 2$ $ $           $ $ $           $ $                     $ $                     $ $               $ $                H ` 0޽h ? ̙33  d`(  d d 0t  XSlide 23"  h d 0&3 4Dab = {abbabaab() : b proper suffix of x,  can be }= {abbabaab}={7} Db = {bbabaab() : b proper suffix of x,  can be }= {bbabaab}={8} E = {baab, aab, ab, b}={11, 12, 13, 14} Aba,1 o Aa,1 (by C2) Aba,1 o Bba (by C5) Aba,1 o Ba (by C2) Aba,1 o Cab (by C2) Aba,1 n Cb (by C4a) 2$ $           $ $           $                 $ $ $($ $ $ $ $ $(($ $ $ $ $(($ $ $ $ $(($ $ $ $ $($ $ $ H d 0޽h ? ̙33]  3h(  h h 0  XSlide 24"   3h 0(3 EAba,1 o Dab (by C2) Aba,1 n Db (by C4a) Aa,1 n Bba (by C1) Aa,1 o Ba (by C5) Aa,1 n Cab (by C3b) Aa,1 n Cb (by C1) Aa,1 n Dab (by C3b) Aa,1 n Db (by C1) ~ 2$ $ $(($ $ $ $ $($ $ $ $ $($ $ $ $ $(($ $ $ $ $($ $ $ $ $($ $ $ $ $($ $ $ $ $($ $ $ H h 0޽h ? ̙33 f^.l( i l l 0O  XSlide 25"   .l 0$&3: Bba o Ba (by C2) Bba o Cab (by C2) Bba n Cb (by C4a) Bba o Dab (by C2) Bba n Db (by C4a) Ba n Cab (by C3b) Ba n Cb (by C1) Ba n Dab (by C3b) Ba n Db (by C1) 2$ $ $(($ $ $ $ $(($ $ $ $ $($ $ $ $ $(($ $ $ $ $($ $ $ $ $($ $ $ $ $($ $ $ $ $($ $ $ $ $($ $ $ H l 0޽h ? ̙33  _ W p( ? p p 04P  XSlide 26"    p 0%3  eCab n Cb (by C1) Cab n Dab (by C5) Cab n Db (by C1) Cb o Dab (by C1) Cb n Db (by C5) Dab n Db (by C1)f 2$ $ $($ $ $ $ $($ $ $ $ $($ $ $ $ $(($ $ $ $ $($ $ $ $ $($ $$ $ f  p 0D'3P  BanAa,1 nCab nDab nBba nAba,1nCb nDb 2 6 10 3 7 1 5 9 4 8 12 13 14 11 2$$($$$($$($$($$($$$($$($$$ $ |B  p TD? |B p TD? `|B p TD? ` |B p TD? H p 0޽h ? ̙33A  |(  | | 0d  XSlide 27"    |  `A ? ?@e    | N$ ?`0q gwww.cas.mcmaster.ca/~franek(  H | 0޽h ? ̙33Y%:x{ XS׶:d aԄ28ѩ *"ZԈaRpjjpZb[:TmpV{VmԠ80#yݝ=Z{ٹaT>(t:=6fS _VN:u>is E`{"B"$;rFOXСO@s3QA<D.uz818NQlHlu]9!@c*iHwgtf>2_cu~['o?ݯz@ ;9G7a!!1m;dkTJR.S7=K6.%3E'2wF܌;R-_;31-9]ګ֯? :cӁgt+:_B!:4z䟵o_qXQ\Z=z>z^sNuEGt^s3b;h.tбJ:ӏYk^37#qnr*tݫwqN ҁ$< -7 zߥ Mc/DNG A"Λ?%GwwՎ[\biǤm?ҿ4=4#o^ztJ(߷K޶X^/YΕAƶ:E5y tP 5T5UCAj +W3RPVVO>ￇGZᣏ>rG=> Vhnnt*XE,$UCUu\P޹ nnUB3RHd Z!#ʦ_J:(J7W -YVc~Vg̈́,F9Sug!D Q-tAd.8YȆ8.4YBZ15ob/g>-Y3ICn[Vczb[Hjo!5< ic!m-J -dw }ECaט32`*BY$a$̩H+=_qD G<\8T:<7b"zFD"wwL2%k!v`I8ynċW BGls_:\۱A|PUJ(Fd!#{$YAjH*T^kEض> >m^5(k Wx&Ob `Z~iT K2ߥ2,p.O-Ob'?OIyAD8*O" \AxHT2 hh°#BŌPiX*vF(" x>xJ ?,L?B%P"T*1JH"T*r[z(h@z={PG_8F8nfK"R' k,@/^/-Q&O9Qh* .rLm3oJ&~&xmvEgQ/&R"_/Lh b0ktŜTcᦩ]?EaɪYYFcTvK3 0].T!.UD*T44;;.#,kn5vO7⊝ gb6L1d69#-O7 |+׊DpqGs@??$+ *Z+r^%O* lx٨//}UZFXق?$+,$4P}1I>TtZi 94b)D (xiBrFn))))搳͒YgXʦʦ+GNLV\|qYW+>VRyO{pDQf};9iַ®&д! <'j^ivff=R^#^Ri;Rfss0)#eDMg=ܬ'nW@ |EYfF1P :aaa}< BrӫoofΥ_{pIdaOzj^W3g2k>^bZ1JDyQvxUX+}OIas T?٦Y*pHGHupu9{p&p۷We+l~OC!SЈx\'=_!>6fֹDZ#N G5.xpko,p=cRe7=|VFt9sr9|zI*r\f9c&L<> 03Fɕ*PZ2f&mbuK~ȩ'\oϊ0O.'^`}@}wB Fi̦1 c7@¹Œc~Q^R٫WCs&&9QC!ҝ7E1==?8H}1:]: E/u1BOw9'ć:boy]r.+jQ&n -g_G(+NZvc`*Mh3MT+/qGLZ[594~g|z/?՟Þ|bNJ6i7_}XO_k;>JAPڵتJÌ=j?-O=q_P7:&WRܧ%c?n.97Ox_tVm8)L`< f>4|ݐ~m6 1FCc!{ױe[#b>TSiii Θn0՘Xf< 4RRr.4?71[0Rca]KN]TڏZMևZ+r|(T֫:N>|\8 ۭ_ZwG]f_&]$Dittt{Y RBV RVLRبث8YR nL #D QF" OִNm:@}w 8藬UԟOUib-LЦjh ڣKϵolPP].Y+m}3মR{"K/!R?Y_ߤ;=퓬=t;7+ AP )E5ba}z䩡`[VܯXY c//@7ũ8,ENS_)奛K?/xGpN)<+}]jgaTCd#d ۍӏ74BoMY&Xk3)5/& 3e`iN01ͯ26WwUfsn7kO5gn,-}fkIQI<, *3+ p9LsB|2oyRiiP0aoRoM żR>CKcJBVҭKϔXF8ilL3.5eƿ}WϰXnjpowLϤ4L09,^f3_5HvlAI g8{mVL̕Yb*vƓ#V R1jC8͍mԩ+MƓOr4'̏l=$ퟙ_êZcl+KzFZoRTo ާT" _AmQE" |4p^LD~|IM&KLQe)Tr&XJj2͹F lL \h%ĘT8>98lAkزU_r!X`?JJ it*ꐒL}՝CCV! &@&*>Sa"0B8XCA * 3! dg¤$*NE> ' jU.h N96UoPCMʵ ׎.֮E]mYMS An.GWۡ;+c]w!KRU_{Y_i!y @0@zf~7 WZrf }aTD&b$cU61hngvZr,dh_ƴ x=A3B:X:'YBnoPBm?hr#2Mx@rU:`Tt)EuԾ ʓYH9 f!7T6-04sBjyeė쟍#jIa9G9_ĥ^TC|~i}T%aTҩR5vX1YRuEL6B*- CNiQzɤ2=#}QȔ6Iq/$ nkAjeTjj0xT!=EQ+FS3LUe+w4O2x@ vF.xT}, wB7^x:v y] ,᫱_2ӥR)c]= 9"y.-Iɔ,;%k,+ɒ%Ν&Kts&'e訹4]ܬLf?pS+uuDKBz3/ڵʨr3 7Y]Y=4EeCN0T ]u%61}gu eЬv0DL&`lVCʦsBhÛ_g3SR歆)Udmf9cal;r3B`jlOCPG[wT!?J<]4_.6s U&d%B!_{T8\xT`ĶX8ۭXP-4IV&ľ@Ƞ̷*+@0O7A>s/.Qūf/Ox="b(a,`40#=^2nH*6LM&: Y$Kdh8At~2*ˣ\ж*%, d̘% DS):0]s̲ٳe3eTF2A[c?/i#008?n=3ynVT6`>\ϧ& & {95 &̳1bF(i]Ni7,ґKFbjgOxvF7Z X ؉n^Sty:he I^3S"^ZR`Z5SdU}~8OՃNR)Noh 5sz;$˱MhZF~f.|5Y]x\\ȕϥc + B^_ŕ['DNJ Rá L+Z[+6IrKpƟ*f7͗b.BXȹf셅D)Q>4ZcU -+uoXH%DkB(Cl}e!c-mO5cYF!шU@i i`q#ß1-'H2rkvBd ҹsZ)%A]Skw.Ϲʰ]}Hor57 q܊֫6;4U/ U"9:zTxv1  b./WT<@D2^@Lbf"rHGyoWaC RU:djBj|5O|5[= "}Zԗ8FP}}STUL-ۍ B I)*x&GEܒ8`C쁩ҙp=34}2h&~Һ|('Nm9`?3@ɪd_u9? Q`QM.RYKQ),lIv"vY_*^> w$ΛUވZ-bGˆ2"2mn`oظgC= 7< ?eQuFs_š5+i?CA۳ΚH\7F({nSf> s+Dnp}ڂ 0L'2lfnHι[W C̗QD>oo2^S:I6TcU nG顛Ӹ|c3u u #]^J!߀gua<|iv5m ^k+u43Zs\fE~9T W/mfUn Buu5yȍֽxX}z }mzPpHTT)IURTGKZ3jRdj.i-ֹ~Y>AX7 &-'Y(sGf1NwW2ʃ̢7ȥ#5EhnյҦ~:`mL"4>XWe!tTYلx=Grj \ebkVW;ﶁ+tCfSJLjWGӎOn}(6MG7d}Ft@sмn FT-a7t*ߋ3M% |܂ \d\ڋ1/vsbE>O9c3zڇ?kЎVŐ0ƼI)CЇfވy)ӒݤuIј}^XH3yɲp]nbV{:뺌.E]]]A]]tmеM@6]vmصM`6!]ۄtmҵMH6ؑKLI=F_"-7({8^%#]ޘm {$hVrKedZ#ɕ/`l!UFj|~WrD5ŕ 5# MVq{)guh])l5g~(xd[2 lYf3< l&dlYOdWlQ"ҋbşLP(G8ar/ RN β\O~g5oVƳ_cuo0~ϔ;Z ~Zv ~[8JsKk.t C :vL.IKpC?:I x<7E%Gi F4zF/"r@ ۇ"e1\(qB=Q-o@ QH#^ME\I@(wwq3S'{N( O?TO?D፞^w/]Jn߸>Hqqr4lZMsf'h lXvCGyilטXg.}K<*13+9|T;(;=8ﺛiS';C78Lqq1#kcƪƍTv9Ržvtqa*踇u^B;O6 r G|$,07?]Y˰ {/&M.5U=3ELgT3_[gl~r 5|~ ߤ!Oh+'04 `h  Suffixes and PrefixesPDr. F. FranekreDr. F. Franekre333Microsoft PowerPointP@i*@b| @`(j G oM  T& &&#TNPP0D & TNPP &&TNPP    --- !---&G&wc ~@  ~ ~ ~0- &Gy& --PP-- Times New Roman  ~ ~ ~0- .62 ~Sorting suffixes of two-pattern!*. .2 strings.--Q9-- Times New Roman  ~ ~ ~0- .(2 F. Franek & W.F. Smyth  ! (  ! .Times New Roman  ~ ~ ~0- .-2 IAlgorithms Research Group    .Times New Roman  ~ ~ ~0- .(2 |Computing and Software!    . .$2 1McMaster University&&    . .!2 LHamilton, Ontario!    . .2 *Canada.--``-- Times New Roman  ~ ~ ~0- .T2 3PSC04, Praha, Czech Republic, August-September 2004       .--h-- Times New Roman  ~ ~ ~0- .2 rSlide 1   .--"System !$ ~-&TNPP &՜.+,D՜.+,X     On-screen ShowMcMaster University  Times New Roman WP MathADefault DesignMicrosoft Visio Drawing(Sorting suffixes of two-pattern stringsNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide TitleNo Slide Title  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles 6> _PID_GUIDAN{6BE5103F-C56B-4B36-A3F7-1C8CFE899E53}%_g Dr. F. Franek  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)=*@PicturesCurrent User-SummaryInformation(PowerPoint Document(DocumentSummaryInformation8