求解一道小公司的OA题

n^2的解法超时

谷歌搜下Z Algorithm...直接用这个算法就可以了。。

看完再顺便掌握下KMP算法 =。=

kmp可以解。
如果你了解KMP中next数组的意义的话，next代表当前index之前的子串中真前缀和真后缀相等的最大index。

如图所示，因为next的意义，a + b + c对应的字符串，是等于a' + b' + c'的。而又因为，a' + b' + c'实际上是原字符串的后缀，所以a' = b, b' = c, c' = d。
而a = a', b = b', c = c'，我们可以得到a =b = c = d。而d的长度是i - next。
也就是说，只要i % d == 0 且i/d为偶数，当前字符串就必定可以写成a + a的形式。这时候就可以找到前缀匹配的长度了。

不知道小帅 发表于 2020-11-11 07:17
kmp可以解。
如果你了解KMP中next数组的意义的话，next代表当前index之前的子串中真前缀和真后缀相等的最 ...

其实俺没有看懂你的解释，但我觉得lz的题目，可以从尾巴开始for loop求next数组，对吗

我怎么那么帅啊 发表于 2020-11-15 10:48
其实俺没有看懂你的解释，但我觉得lz的题目，可以从尾巴开始for loop求next数组，对吗

你是说reverse吗？还是？

KMP求next数组不是要利用之前的结果嘛。原本是for (int i = 0; i < string.length(); i++) // 对于每一个以i为结尾的string 找他的最大common, 然后利用i - 1的结果来算 i 的结果。
我觉得这个题意，for (int i = s.length() - 1; i >= 0; i--) 就可以了，帮我看看这样对吗