Video 5-3: §5.2 Periodicity (part 2)

0:00 Periodicity Lemma

0:03 we left off last time in the middle of the section on periodicity with this periodicity lemma and what that says is if if you have a string s and it has two periods it satisfies this shifting with uh two periods p and q and uh they're not both they're not too big then indeed you can take the greatest common divisor of those two periods which is a smaller number um and then this will also be a period of the of the string you will look in more detail um at this at this lemma in the tutorials so i don't want to go into further details of the proof but i want to remark that smaller periods are of course like in this case the three are of course somewhat more telling about a string because a small period means a very long overlap and these long overlaps are things that we can use or exploit so what this lemma tells you is if you have two periods and they are somehow related their greatest common divisor has is not one of them then you get a new stronger period just automatically from this for example if if you would be able to show that the string has a period of three and five those are co-prime so the

0:52 Periodicity and KMP

1:34 greatest common divisor is one that means the string is all a's it's just a repeated many times n time m times that's a fairly strong statement coming from this somewhat more innocent observation that a string has period three and five so this will be uh used under the hood in in these algorithms now uh this was a nice definition we have period periods in strings um but what does this really tell us about strings and there are two distinct regimes that people found useful to exploit algorithmically and these are the periodic and the aperiodic case and here we are really interested in the smallest period this is the only um p will be the most of most of the time here because that's just the the strongest statement remember it's the longest overlap so that's the the most telling statement about the string if this shortest period is less than half of the string

1:53 Periodic strings

2:48 that means we can overlap a string with itself and there's more than half left okay maybe i should be a slight bit more precise here in the lengths if i can do this with my string and these are all the same

3:08 well because this is at least half of the string i can find the string again i can do the same i can shift this over another time and now what you see is this green part is also this green part but hey this says it's equal to this part

3:33 which is uh also here and so that blue part is the same as the green part which occurs here another time uh but this has to be the same as this and this has to be the same as as this so also this third repetition this is all the same okay so uh graphically speaking this and this

4:10 these are all the same strings there is exactly identical and so uh what this means is there's a smaller string f a factor in in the terminology that people use for this this factor is is only of length p which might be much shorter than n and s is essentially formed by repeating this factor over and over until you have n characters so as you as you see here we have three times the same string and then there's some [Music] left over part at the end which again is it's the start of the green part again but it's not an entire copy okay and so uh this definitely means that s is repetitive in that it consists of a factor that you just keep repeating and if you think about it this uh we should be able to exploit this in string matching if you have a long pattern that you're trying to find but the pattern actually consists of just repeating a small same string over and over we might as well search for the small pattern and combine the matches okay so intuitively this helps for string matching

5:44 there's also the other case namely if this is not true if the smallest period is longer than one-half then we cannot do this because if we shift a string over by more than half of the length if we would do this a second time it would look like this and there's no connection between the first and the third copy so the only thing we can say about this string is that we cannot write it in this way we cannot find a factor and repeat that at least twice and then have another prefix of it the only thing we can say is that this is not true so while the first case a repetitive string seems to help for string matching intuitively and also you can exploit this fairly easily algorithmically the second case seems not to help how should the knowledge about a periodicity help us in string matching

6:43 Clicker Question

6:46 before we explore this question i want to head over and get you guys active so here is a string um and i just want to know if this is repetitive or not and i only want to show you the results at the end so you have um

7:25 so we had some 30 votes for the uh intro question so i would hope that we get to our usual 25 for this question as well come on guys if you don't know take no clue

7:47 this is meant to be your first in intuitive answer to this aha there we go 25. uh a roughly equal split um the correct answer is no but um

8:19 the the trick at this point is this string definitely looks very repetitive right it's a a lot of a's and that just won't be sticked at the end um but that is not enough for being periodic in the precise sense how we defined it the the thing is here

8:45 that the precise definition is it's periodic in this sense if you can overlap it with itself and if you try to overlap this string with itself if you do a lot of a's and then at the end of b try to overlap this with i don't know say half the length you would still have to put somewhere this a above a b that never works this string has has no non-trivial period you can never align the b with anything the only option you have is to shift it entirely behind itself this formerly qualifies as the period n but it's not an interesting one so uh the reason i post this fairly simple question is is to warn you um in this with these topics sometimes people choose very intuitive terms like periodic in this case uh but be careful not to substitute an intuitive meaning for the formal meaning from the definition the term is supposed to help you and sometimes these are chosen well and sometimes these are chosen not so well not so helpful but you should look behind this superficial name you have to look at the actual definition and in this case even though this string surely is repetitive in some sense it's not periodic