Completing the New Periodicity Lemma

摘要: The “Three Squares Lemma” (Crochemore and Rytter 1995) famously explored the consequences of supposing that three squares occur at same position in a string. Essentially, it showed this phenomenon could not unless longest was least sum lengths other two. More recently, several papers (Fan et al. 2006; Franek, Fuller, 2012; Kopylova Smyth Simpson 2007) have greatly extended result to “New Periodicity (NPL) by only two position, with third occurring neighbourhood right. proof NPL involves fourteen subcases, twelve which been proven over last seven years. In thesis, we prove final remaining.