20
\$\begingroup\$

Local periods

Take a non-empty string s. The local period of s at index i is the smallest positive integer n such that for each 0 ≤ k < n, we have s[i+k] = s[i-n+k] whenever both sides are defined. Alternatively, it is the minimal length of a nonempty string w such that if the concatenation w w is placed next to s so that the second copy of w begins at index i of s, then the two strings agree wherever they overlap.

As an example, let's compute the local period of s = "abaabbab" at (0-based) index 2.

  • Try n = 1: then s[2+0] ≠ s[2-1+0], so this choice is not correct.
  • Try n = 2: then s[2+0] = s[2-2+0] but s[2+1] ≠ s[2-2+1], so this is also not correct.
  • Try n = 3: then s[2+0-3] is not defined, s[2+1] = s[2-3+1] and s[2+2] = s[2-3+2]. Thus the local period is 3.

Here is a visualization of the local periods using the second definition, with semicolons added between the two copies of w for clarity:

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

Note that w is not necessarily a substring of s. This happens here in the index-4 case.

The task

Your input is a nonempty string s of lowercase ASCII characters. It can be taken as a list of characters if desired. Your output shall be the list containing the local period of s at each of its indices. In the above example, the correct output would be [1,2,3,1,6,1,3,2].

The lowest byte count in each language wins. Standard rules apply.

Test cases

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]
\$\endgroup\$
  • \$\begingroup\$ @Arnauld You can always find a w with the same length as s. In the case of qwertyuiop, w will be a rotated version of qwertyuiop. See also the example at index 4: w is not necessarily a substring of s. \$\endgroup\$ – Zgarb Feb 15 '18 at 9:29
  • \$\begingroup\$ That makes sense. I misread the challenge. \$\endgroup\$ – Arnauld Feb 15 '18 at 9:31
  • \$\begingroup\$ Imaginary bonus for a linear time solution! (someone else may offer a real bounty, so keep trying) \$\endgroup\$ – user202729 Feb 15 '18 at 9:40
  • \$\begingroup\$ Really neat challenge, but I wonder if it would make more sense to define the local period of each position between two characters (i.e. wherever the ; is in your example). That would get rid of the leading 1. \$\endgroup\$ – Martin Ender Feb 15 '18 at 9:49
  • \$\begingroup\$ @MartinEnder That would be conceptually cleaner, but this definition makes it easier to produce the output by looping over the string, and the output won't be empty. \$\endgroup\$ – Zgarb Feb 15 '18 at 10:06
4
\$\begingroup\$

Retina, 89 86 bytes

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

Try it online! Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

.
$`¶$<'¶

Split the input at each character, creating a pair of lines, one for the prefix and one for the suffix of the prefix.

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

Run the rest of the script on each resulting pair.

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

Find all overlapping matches and list the results. (See below.)

G`.

Discard the empty match.

%C`.

Take the length of each match.

N`

Sort numerically.

0G`

Take the smallest.

The matching works by splitting the prefix and suffix into three parts. There are four valid cases to consider:

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

The regex therefore only allows A and C to match on one side at a time.

\$\endgroup\$
4
\$\begingroup\$

Java 8, 167 154 152 bytes

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 bytes thanks to @ceilingcat.

Try it online.

Explanation:

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
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 84 bytes

Takes input as an array of characters.

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)

Test cases

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]

\$\endgroup\$
  • \$\begingroup\$ I'm not sure if taking an array of characters is allowed, are you sure they're not just 1-character strings? \$\endgroup\$ – Erik the Outgolfer Feb 15 '18 at 11:12
  • \$\begingroup\$ @EriktheOutgolfer There's no character type in JS, so yes: it's technically an array of 1-character strings. My understanding is that if it quacks like a string, it's a string. (Here is a meta post about that, but a more relevant one may exist -- or one that actually contradicts my assumption.) \$\endgroup\$ – Arnauld Feb 15 '18 at 11:26
  • 1
    \$\begingroup\$ Or to put it in other words: this is as close as we can get to a list of characters in JS, which was explicitly allowed by the OP. \$\endgroup\$ – Arnauld Feb 15 '18 at 12:48
1
\$\begingroup\$

Ruby, 104 102 bytes

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

Try it online!

A lambda accepting a string and returning an array.

-2 bytes: Swap range endpoints with index bound guards

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
  }
}
\$\endgroup\$
1
\$\begingroup\$

Japt, 33 32 bytes

Saved 1 byte thanks to @Shaggy

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

Test it online!

Explanation

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

My first thought was to just compare each character in the left substring with the corresponding char in the right substring, as in the JS answer. That wouldn't work, however, as Japt's method to get a character just wraps to the other end of the string if the index is negative or too large.

Instead, my solution builds a regex out of the second substring and tests it on the first substring. Let's take the 5th item in test-case abaabbab as an example:

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..$/

The main trick is that ^ can match infinitely, up until an actual character is matched. This lets us ignore any number of characters from the start of the regex, while ensuring that the rest are all matched consecutively, finishing at the end of the test string.

I'm not sure I've explained this very well, so please let me know if there's anything you'd like clarified, or anything else that should be explained.

\$\endgroup\$
  • \$\begingroup\$ 32 bytes. \$\endgroup\$ – Shaggy Feb 21 '18 at 10:50
  • \$\begingroup\$ @Shaggy Thanks, that semicolon was bugging me :P \$\endgroup\$ – ETHproductions Feb 21 '18 at 15:23
1
\$\begingroup\$

C (gcc), 143 142 140 139 128 126 123 bytes

  • Saved a byte. Golfed !b&&printf to b||printf.
  • Saved two bytes thanks to Kevin Cruijssen. Removed the for loop body parentheses by juggling the printf placement.
  • Saved a byte. Golfed b+=S[i+k]!=S[i-n+k] to b|=S[i+k]-S[i-n+k].
  • Saved eleven bytes. Removed the need of l=strlen(S) by conditioning both string handling loop to break when reaching the string's end (a null byte '\0').
  • Saved two bytes. Golfed i-n+k>~0 to i-n>~k.
  • Saved three bytes thanks to ceilingcat; b||printf("|"),n++ is equivalent to 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];}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 2, 115 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.