задача со строкой

[Hekumok]

Вам дана строка. Циклическим сдвигом строки s длины n называется строка, полученная из исходной путём отбрасывания первых 0 ≤ k < n символов и приписывания их в конец. Необходимо посчитать, сколько раз среди всех циклических сдвигов строки встречается лексикографически минимальный циклический сдвиг.
Ограничение по времени: 0.6 секунд
Ограничение по памяти: 256 мегабайт
Формат входного файла:
Единственная строка входного файла содержит строку S. Она непуста, состоит из маленьких латинских букв, и её длина не превосходит 10 000 000.
Формат выходного файла:
Выведите единственное число – искомое количество минимальных циклических сдвигов.

Пробовал таким способом, но выдаёт ошибку(( Fatal error: Maximum execution time of 30 seconds exceeded in C:\Program Files (x86)\My Programms\EasyPHP-DevServer-13.1VC11\data\localweb\scripts\5\5.php on line 5

$S = preg_split('/\s+/', trim(file_get_contents('input.txt')))[0] ;
$str = $S ;
$n = 1 ;
for($i = 0; $i < strlen($S); $i++) {
	$S = substr($S, 1) . substr($S, 0, 1) ;
	if($S < $str) {
		$str = $S ;
		$n = 1 ;
	} else if($S == $str)
		$n++ ;
} ;
echo $n ;