Местные периоды

Возьмите непустую строку s . Локальный период из S в индексе я это наименьшее натуральное число п такое , что для каждого 0 ≤ к <п , мы имеем с [I + K] = s [я-п + K] всякий раз , когда обе стороны определены. С другой стороны , это минимальная длина непустой строки ж такое , что если конкатенация WW стоит рядом с так , что второй экземпляр ш начинается с индекса я в с , то две строки соглашаются , где они перекрываются.

В качестве примера давайте вычислим локальный период s = "abaabbab" с индексом 2 (на основе 0).

• Попробуйте n = 1 : тогда s [2 + 0] ≠ s [2-1 + 0] , поэтому этот выбор не верен.
• Попробуйте n = 2 : тогда s [2 + 0] = s [2-2 + 0], но s [2 + 1] ≠ s [2-2 + 1] , так что это тоже не правильно.
• Попробуйте n = 3 : тогда s [2 + 0-3] не определено, s [2 + 1] = s [2-3 + 1] и s [2 + 2] = s [2-3 + 2] . Таким образом, местный период равен 3.

Вот визуализация локальных периодов с использованием второго определения, с точкой с запятой, добавленной между двумя копиями w для ясности:

index      a b a a b b a b      period
 0       a;a                     1
 1       b a;b a                 2
 2       a a b;a a b             3
 3             a;a               1
 4     b b a b a a;b b a b a a   6
 5                 b;b           1
 6               a b b;a b b     3
 7                   b a;b a     2

Обратите внимание, что w не обязательно является подстрокой s . Это происходит здесь, в случае индекса 4.

Задание

Ваш вклад непустой строки s из строчных символов ASCII. При желании его можно принять за список символов. Ваш вывод должен быть списком, содержащим локальный период s для каждого из его индексов. В приведенном выше примере правильный вывод будет [1,2,3,1,6,1,3,2] .

Наименьшее количество байтов в каждом языке выигрывает. Применяются стандартные правила игры в гольф .

Контрольные примеры

a -> [1]
hi -> [1, 2]
www -> [1, 1, 1]
xcxccxc -> [1, 2, 2, 5, 1, 3, 2]
abcbacb -> [1, 4, 7, 7, 7, 3, 3]
nininini -> [1, 2, 2, 2, 2, 2, 2, 2]
abaabbab -> [1, 2, 3, 1, 6, 1, 3, 2]
woppwoppw -> [1, 4, 4, 1, 4, 4, 4, 1, 4]
qwertyuiop -> [1, 10, 10, 10, 10, 10, 10, 10, 10, 10]
deededeededede -> [1, 3, 1, 5, 2, 2, 5, 1, 12, 2, 2, 2, 2, 2]
abababcabababcababcabababcaba -> [1, 2, 2, 2, 2, 7, 7, 7, 7, 2, 2, 2, 19, 19, 5, 5, 2, 5, 5, 12, 12, 2, 2, 2, 7, 7, 5, 5, 2]

Retina , 89 86 байт

.
$`¶$<'¶
/(^|.+)¶.+/_(Lw$`^(.+)?(.*)(.+)?¶(?(1)|(.*))\2(?(3)$)
$2$3$4
G`.
%C`.
N`
0G`

Попробуйте онлайн! Редактировать: 3 байта сохранены благодаря @MartinEnder. Объяснение:

.
$`¶$<'¶

Разделите ввод для каждого символа, создав пару строк, одну для префикса и одну для суффикса префикса.

/(^|.+)¶.+/_(

Запустите оставшуюся часть сценария для каждой полученной пары.

Lw$`^(.+)?(.*)(.+)?¶(?(1)|(.*))\2(?(3)$)
$2$3$4

Найдите все совпадающие совпадения и перечислите результаты. (См. ниже.)

G`.

Откажитесь от пустого матча.

%C`.

Возьмите длину каждого матча.

N`

Сортировать численно.

0G`

Бери самый маленький.

Сопоставление работает путем разделения префикса и суффикса на три части. Есть четыре допустимых случая для рассмотрения:

AB|BC   B matches B to the left and B to the right
B|ABC   AB matches [A]B to the left and AB to the right
ABC|B   BC matches BC to the left and B[C] to the right
BC|AB   ABC matches [A]BC to the left and AB[C] to the right

Поэтому регулярное выражение позволяет только A и C совпадать только на одной стороне одновременно.

Java 8, 167 154 152 байта

s->{int l=s.length,r[]=new int[l],i=0,n,k;for(;i<l;r[i++]=n)n:for(n=0;;){for(k=++n;k-->0;)if(i+k<l&i+k>=n&&s[i+k]!=s[i-n+k])continue n;break;}return r;}

-2 байта благодаря @ceilingcat .

Попробуйте онлайн.

Объяснение:

s->{                          // Method with char-array parameter and int-array return-type
  int l=s.length,             //  Length of the input-array
      r[]=new int[l],         //  Result-array of the same size 
      i=0,n,k;                //  Integers `i`, `n`, and `k` as defined in the challenge
  for(;i<l;                   //  Loop `i` in the range [0, `l`):
      r[i++]=n)               //    After every iteration: Add `n` to the array
    n:for(n=0;;){             //   Inner loop `n` from 0 upwards indefinitely
      for(k=++n;k-->0;)       //    Inner loop `k` in the range [`n`, 0]:
                              //    (by first increasing `n` by 1 with `++n`)
        if(i+k<l&i+k>=n)      //     If `i+k` and `i-n+k` are both within bounds,
           &&s[i+k]!=s[i-n+k])//     and if `s[i+k]` is not equal to `s[i-n+k]`:
          continue n;         //      Continue loop `n`
                              //    If we haven't encountered the `continue n` in loop `k`:
      break;}                 //     Break loop `n`
  return r;}                  //  Return the result

JavaScript (ES6), 84 байта

Принимает ввод как массив символов.

s=>s.map((_,i)=>s.some(_=>s.every(_=>k<j|!s[k]|s[k-j]==s[k++]|k-i>j,++j,k=i),j=0)*j)

Контрольные примеры

let f =

s=>s.map((_,i)=>s.some(_=>s.every(_=>k<j|!s[k]|s[k-j]==s[k++]|k-i>j,++j,k=i),j=0)*j)

console.log(JSON.stringify(f([...'a']))) // [1]
console.log(JSON.stringify(f([...'hi']))) // [1, 2]
console.log(JSON.stringify(f([...'www']))) // [1, 1, 1]
console.log(JSON.stringify(f([...'xcxccxc']))) // [1, 2, 2, 5, 1, 3, 2]
console.log(JSON.stringify(f([...'abcbacb']))) // [1, 4, 7, 7, 7, 3, 3]
console.log(JSON.stringify(f([...'nininini']))) // [1, 2, 2, 2, 2, 2, 2, 2]
console.log(JSON.stringify(f([...'abaabbab']))) // [1, 2, 3, 1, 6, 1, 3, 2]
console.log(JSON.stringify(f([...'woppwoppw']))) // [1, 4, 4, 1, 4, 4, 4, 1, 4]
console.log(JSON.stringify(f([...'qwertyuiop']))) // [1, 10, 10, 10, 10, 10, 10, 10, 10, 10]
console.log(JSON.stringify(f([...'deededeededede']))) // [1, 3, 1, 5, 2, 2, 5, 1, 12, 2, 2, 2, 2, 2]
console.log(JSON.stringify(f([...'abababcabababcababcabababcaba']))) // [1, 2, 2, 2, 2, 7, 7, 7, 7, 2, 2, 2, 19, 19, 5, 5, 2, 5, 5, 12, 12, 2, 2, 2, 7, 7, 5, 5, 2]

Рубин , 104 102 байта

->s{l=s.size-1
(0..l).map{|i|n=0
loop{n+=1
(n-i..l-i).all?{|k|k<0||k>=n||s[i+k]==s[i-n+k]}&&break}
n}}

Попробуйте онлайн!

Лямбда, принимающая строку и возвращающая массив.

-2 байта: поменять местами конечные точки с ограничителями индекса

Ungolfed:

->s{
  l=s.size-1                # l is the maximum valid index into s
  (0..l).map{ |i|           # i is the current index
    n=0                     # n is the period being tested
    loop{                   # Repeat forever:
      n+=1                  # Increment n
      (n-i..l-i).all?{ |k|  # If for all k where i+k and i-n+k are valid indexes into s
        k<0 || k>=n ||      #   We need not consider k OR
          s[i+k]==s[i-n+k]  #   The characters at the relevant indexes match
      } && break            # Then stop repeating
    }
  n                         # Map this index i to the first valid n
  }
}

Japt , 33 32 байта

Сохранено 1 байт благодаря @Shaggy

¬Ë@¯E f'$iUtED ú.D r."($&|^)"}aÄ

Проверьте это онлайн!

объяснение

¬Ë@¯E f'$iUtED ú.D r."($&|^)"}aÄ   Implicit: U = input string
¬Ë                                 Split the input into chars, and map each index E to
  @                          }aÄ     the smallest positive integer D where
   ¯E                                  the first E chars of U
      f                                matches the regex formed by
          UtED                         taking D chars of U from index E,
                ú.D                     padding to length D with periods,
                    r."($&|^)"          replacing each char C with "(C|^)",
        '$i                             and placing a '$' at the very end.

Моей первой мыслью было просто сравнить каждый символ в левой подстроке с соответствующим символом в правой подстроке, как в ответе JS. Однако это не сработает, поскольку метод Japt для получения символа просто переносится на другой конец строки, если индекс отрицательный или слишком большой.

Вместо этого мое решение создает регулярное выражение из второй подстроки и проверяет его на первой подстроке. Давайте возьмем 5-й элемент в тест-кейсе abaabbabв качестве примера:

abaabbab
    ^ split point -> abaa for testing regex, bbab for making regex

   slice  regex                              matches abaa
1. b      /(b|^)$/                           no
2. bb     /(b|^)(b|^)$/                      no
3. bba    /(b|^)(b|^)(a|^)$/                 no
4. bbab   /(b|^)(b|^)(a|^)(b|^)$/            no
5. bbab.  /(b|^)(b|^)(a|^)(b|^)(.|^)$/       no
6. bbab.. /(b|^)(b|^)(a|^)(b|^)(.|^)(.|^)$/  yes: /^^ab..$/

Основной трюк в том, что он ^может совпадать бесконечно, вплоть до фактического соответствия персонажа. Это позволяет нам игнорировать любое количество символов от начала регулярного выражения, в то же время гарантируя, что все остальные сопоставляются последовательно, заканчивая в конце тестовой строки.

Я не уверен, что объяснил это очень хорошо, поэтому, пожалуйста, дайте мне знать, если есть что-то, что вы хотели бы уточнить, или что-то еще, что следует объяснить.

C (gcc) , 143 142 140 139 128 126 123 байта

• Сохраненный байт. Гольф !b&&printfв b||printf.
• Сохранено два байта благодаря Кевину Круйссену . Убрал forкруглые скобки тела цикла, манипулируя printfразмещением.
• Сохраненный байт. Гольф b+=S[i+k]!=S[i-n+k]в b|=S[i+k]-S[i-n+k].
• Сохранено одиннадцать байтов. Устранена необходимость в том l=strlen(S), чтобы оба цикла обработки строк обрывались при достижении конца строки (нулевой байт '\0').
• Сохранено два байта. Гольф i-n+k>~0в i-n>~k.
• Сохранено три байта благодаря функциюcatcat ; b||printf("|"),n++эквивалентно n+=b||printf("|").

i,b,k,n;f(char*S){for(i=~0;S[++i];)for(b=n=1;b;n+=b||printf("%d,",n))for(b=k=0;k<n&&S[i+k];k++)b|=n-i>k?0:S[i+k]-S[i-n+k];}

Попробуйте онлайн!

Python 2 , 115 байт

lambda s:[min(j+1for j in R(len(s))if all(s[k+~j]==s[k]for k in R(i,i-~j)if len(s)>k>j))for i in R(len(s))]
R=range

Попробуйте онлайн!