Video 5-2: §5.2 Periodicity

0:03 so we need new ideas and in this subsection i want to briefly introduce one new idea that at first seems to have nothing to do with parallelism but it will later enable a different method how to do string matching and that will be easier to parallelize and that idea is periodicity so what does it mean that a string is periodic maybe you have an intuition what that means but um i would like you to basically forget that intuition for now and uh pay pay close attention to the precise definition that is that is given here on the slide uh so we say a string has a period p if this is the case there is an a position i so that if i start f sorry for all positions i if i uh read the character at that position and i jump forward by p i get the same character okay now this is a definition and some uh some values don't make much sense zero is always a trivial period because then we're just claiming as of i's as of i great that's always true uh and any number greater than n is a trivial period because um we assume so we require this well this is uh is written here we only require this

1:34 for positions that are between zero and n minus p and if if p is bigger than n that this is empty so we're not claiming anything so interesting periods have to be between one and length of the pattern and well here's an example this string has a period of length six because if you shift the same string by six positions you get matches in all the positions that remain of course we don't insist on matching anything up here where the strings are not really present here's a different string that has a smaller period three so if you shift it by three positions you notice that this all matches up um if you check carefully okay that is uh that's periodicity um it's a simple definition yeah but it will it will help us in the end to make a parallel string matching method um one one interesting observation that might be obvious from these kinds of pictures almost is is this little lemma it's this statement that um a string has a shortest period p

3:06 if this is a longest prefix that is also a suffix so we take um the the prefix that has the first that leaves off the last p characters and we want that this is the longest prefix that is also a suffix of this so we also take the string

3:45 so this is the string we're looking at here this is the string we're looking at here and we like that this is the longest prefix that's the suffix of this thing oh my gosh you have to digest this

4:01 so you want to align these like this so that means there is again this this overlap here where they match and because this is of the same length um i was actually a bit imprecise in drawing this this should be the same length okay and what that means is there's a connection with our famous and favorite kmp algorithm the minimal period here if that is p that means fail of the final character of the entire string is um n minus p

4:49 because that's um well you have you have to go back to the the definition remember from unit 4 there was this little red box where i said please memorize this and that said fail is well you take a prefix of the pattern and you find the shift so that this is the this is the overlap the longest overlap you can produce by shifting this to the right that's exactly the same picture though there's not not much thought going into this you just have to remember the definitions here so in a sense periodicity is just a known concept rephrased slightly differently

5:30 and we'll continue talking about periodicity a bit more and how to use it next week