Okresy lokalne

Weź niepusty ciąg s . Lokalny okres od s o indeksie i jest najmniejszym dodatnia n takie, że dla każdego 0 ≤ k <n , mamy s [I + K] = s [n + i, k] , gdy obie strony są określone. Alternatywnie, jest to minimalna długość łańcucha niepusty wag taki sposób, że gdy powiązanie WW znajduje się obok s tak, że druga kopia w rozpoczyna się wskaźnika i w s , a następnie dwa ciągi zgadzają gdzie zachodzą one na siebie.

Jako przykład, obliczmy lokalny okres s = "abaabbab" przy (0) indeksie 2.

• Spróbuj n = 1 : następnie s [2 + 0] ≠ s [2-1 + 0] , więc ten wybór jest nieprawidłowy.
• Spróbuj n = 2 : następnie s [2 + 0] = s [2-2 + 0] ale s [2 + 1] ≠ s [2-2 + 1] , więc to również nie jest poprawne.
• Próby n = 3 : I y [2 + 0-3] nie jest zdefiniowana, S [2 + 1] = s [3/2 + 1] i S [2 + 2] = s [2-3 + 2] . Tak więc okres lokalny wynosi 3.

Oto wizualizacja okresów lokalnych z wykorzystaniem drugiej definicji, z średnikami dodanymi pomiędzy dwiema kopiami w dla jasności:

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

Zauważ, że w niekoniecznie jest podciągiem s . Dzieje się tak tutaj w przypadku indeksu-4.

Zadanie

Twój wkład jest niepusty ciąg s z małych znaków ASCII. W razie potrzeby można go traktować jako listę znaków. Twój wynik powinien być listą zawierającą lokalny okres s dla każdego z jego wskaźników. W powyższym przykładzie poprawny wynik wyniósłby [1,2,3,1,6,1,3,2] .

Najniższa liczba bajtów w każdym języku wygrywa. Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

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]

Siatkówka , 89 86 bajtów

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

Wypróbuj online! Edycja: Zapisano 3 bajty dzięki @MartinEnder. Wyjaśnienie:

.
$`¶$<'¶

Podziel dane wejściowe na każdy znak, tworząc parę linii, jedną dla prefiksu i jedną dla sufiksu prefiksu.

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

Uruchom resztę skryptu dla każdej wynikowej pary.

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

Znajdź wszystkie pokrywające się mecze i wyświetl wyniki. (Patrz poniżej.)

G`.

Odrzuć puste dopasowanie.

%C`.

Weź długość każdego meczu.

N`

Sortuj numerycznie.

0G`

Weź najmniejszy.

Dopasowywanie polega na podzieleniu prefiksu i sufiksu na trzy części. Należy rozważyć cztery ważne przypadki:

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

Wyrażenie regularne pozwala więc dopasować A i C tylko z jednej strony na raz.

Java 8, 167 154 152 bajtów

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 bajty dzięki @ceilingcat .

Wypróbuj online.

Wyjaśnienie:

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 bajtów

Pobiera dane wejściowe jako tablicę znaków.

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)

Przypadki testowe

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]

Rubinowy , 104 102 bajtów

->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}}

Wypróbuj online!

Lambda akceptuje ciąg i zwraca tablicę.

-2 bajty: Zamień punkty końcowe zakresu za pomocą osłon związanych z indeksem

Nie golfowany:

->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 bajty

Zaoszczędzono 1 bajt dzięki @Shaggy

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

Przetestuj online!

Wyjaśnienie

¬Ë@¯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.

Moją pierwszą myślą było porównanie każdego znaku w lewym podciągu z odpowiednim znakiem w prawym podciągiem, jak w odpowiedzi JS. Nie działałoby to jednak, ponieważ metoda Japt, aby uzyskać znak, po prostu zawija się na drugi koniec łańcucha, jeśli indeks jest ujemny lub zbyt duży.

Zamiast tego moje rozwiązanie buduje wyrażenie regularne z drugiego podłańcucha i testuje je na pierwszym podciągu. Weźmy na przykład piąty element w przypadku testowym 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..$/

Główną sztuczką jest to ^ można dopasowywać nieskończenie długo, aż do dopasowania postaci. To pozwala nam zignorować dowolną liczbę znaków od początku wyrażenia regularnego, zapewniając jednocześnie, że wszystkie pozostałe są dopasowywane kolejno, kończąc na końcu łańcucha testowego.

Nie jestem pewien, czy dobrze to wytłumaczyłem, więc proszę dać mi znać, jeśli jest coś, co chciałbyś wyjaśnić, lub cokolwiek innego, co powinno zostać wyjaśnione.

C (gcc) , 143 142 140 139 128 126 123 bajtów

• Zapisano bajt. Grał !b&&printfw golfa b||printf.
• Zaoszczędził dwa bajty dzięki Kevinowi Cruijssenowi . Usunięto fornawiasy korpusu pętli, żonglując printfumieszczeniem.
• Zapisano bajt. Grał b+=S[i+k]!=S[i-n+k]w golfa b|=S[i+k]-S[i-n+k].
• Zapisano jedenaście bajtów. Usunięto potrzebę l=strlen(S)warunkowania obu pętli obsługi ciągów, aby przerywały się po osiągnięciu końca łańcucha (bajt zerowy'\0' ).
• Zapisano dwa bajty. Grał i-n+k>~0w golfa i-n>~k.
• Oszczędność trzech bajtów dzięki pułapowi cat ; b||printf("|"),n++jest równoważne z 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];}

Wypróbuj online!

Python 2 , 115 bajtów

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

Wypróbuj online!