Local periods of strings

Question

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 code-golf 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]

Answer 1

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.

Answer 2

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

Answer 3

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]

Answer 4

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

Answer 5

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.

Answer 6

C (gcc), 143 142 140 139 128 126 123 119 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("|").
• Saved four bytes thanks to ceilingcat.

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

Try it online!

Answer 7

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!