Period

Basic Concept

Given a string \(w\), period of \(w\) is \(p \in \{1, \dots, |w| \}\) such that \(w[i] = w[i+p]\) for all \(1 \leq i \leq |w|-p\) ．

Note

For example, 5, 7, and 8 are periods of \(abaababa\).

Given a string \(w\), \(|w|\) is a period of \(w\), thus \(w\) have at least one period. The smallest value of period of \(w\) called smallest period and denoted by \(period(w)\).

Note

For example, \(period(abaababa) = 5\).

w =
・length(w) = dummy
・period(w) = dummy

Period has relation with Border.

Algorithm

Algorithm to find smallest period of gives string

  • Naive algorithm

 1      var n = w.length;
 2      if ( n == 0 ) {
 3	return 0;
 4      }	       
 5      for( var p=1; p <= n; p++ ) {
 6        var flag = true;
 7        for(var i=0; i < n-p; i++ ){
 8          if ( w[i] != w[i+p] ) {
 9            flag = false;
10            break;
11          }
12        }
13        if ( flag == true ) {
14          return p;
15        }
16      }
17    };
18
  • Code in python

    /Scripts/Python/period.py

References