字符串的局部周期

Question

局部周期

取一个非空字符串s。指数i的s的局部周期是最小的正整数 n，使得对于每一个0≤k，无论何时定义双方，我们都有s = s。或者，它是一个非空字符串w的最小长度，这样如果连接w w放置在<>S>旁边，那么<>w的第二份拷贝开始于i的s的索引处，那么这两个字符串在它们重叠的地方一致。

例如，让我们计算s = "abaabbab"在(0-)索引2处的本地周期。

• 尝试n = 1：那么s≠s，所以这个选择是不正确的。
• 尝试n = 2：那么s = s但是s≠s，所以这也是不正确的。
• 尝试n = 3：然后s未定义，s = s和s =<#>s。因此，局部周期为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的情况下。

任务

您的输入是小写ASCII字符的非空字符串s。如果需要，可以将其视为字符列表。您的产出将是包含s的本地周期的列表，在其每个指标中。在上面的例子中，正确的输出应该是<#>。

每种语言中的最低字节数获胜。适用标准的密码-高尔夫规则。

测试用例

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

JavaScript (ES6)，84字节

将输入作为字符数组。

s=>s.map((_,i)=>s.some(_=>s.every(_=>kj,++j,k=i),j=0)*j)

测试用例

let f =

s=>s.map((_,i)=>s.some(_=>s.every(_=>kj,++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 2

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

在网上试试！