Редактирование: Z-функция

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 161: Строка 161:
  
 
===Псевдокод===
 
===Псевдокод===
  '''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[n])
+
  '''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[])
 +
  '''int''' n = P.length
 
   '''int'''[] Z = '''int'''[n]
 
   '''int'''[] Z = '''int'''[n]
 
   '''for''' i = 1 '''to''' n - 1
 
   '''for''' i = 1 '''to''' n - 1
Строка 167: Строка 168:
 
         Z[i - P[i] + 1] = P[i]
 
         Z[i - P[i] + 1] = P[i]
 
   Z[0] = n
 
   Z[0] = n
   '''int''' i = 1
+
   '''int''' t
   '''while''' i < n
+
   '''for''' i = 1 '''to''' n - 1
      '''int''' t = i
+
      t = i
 
       '''if''' Z[i] > 0
 
       '''if''' Z[i] > 0
 
         '''for''' j = 1 '''to''' Z[i] - 1
 
         '''for''' j = 1 '''to''' Z[i] - 1
Строка 176: Строка 177:
 
             Z[i + j] = min(Z[j], Z[i] - j)
 
             Z[i + j] = min(Z[j], Z[i] - j)
 
             t = i + j
 
             t = i + j
       i = t + 1
+
       i = t
 
   '''return''' Z
 
   '''return''' Z
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: