深圳iava外包越来越低了，5到10年竟然最多13K或者15K了，比前几年还低|len|str|代码|回文|字符串|深圳市

深圳Java外包这行情，已经不是卷了，是往回倒车。5到10年经验，开价还卡在13K、15K，乍一看像在招人，细一看像在测试谁还没断奶。

前几年大家还吐槽外包累、杂、没归属感，但钱起码还能撑住脸面。现在倒好，活一点没少，价倒先砍了。网友也很损，有人说这工资放深圳，房租和通勤先吃一半，剩下那点钱，连“多年经验”四个字都显得心酸。还有人说，企业现在不是招Java，是在淘性价比最高的老黄牛。

HR把需求写得天花乱坠，候选人点开一看，估计眼皮都跳一下。真要这个价，别聊什么发展了，先问问这班上着图啥。

算法题：strong> 最短回文串

字符串一长，回文题最容易写成“能过样例，过不了大数据”。

“最短回文串”就是这种。题目要求很克制：给你一个字符串 s ，只能在头部添加字符，把它补成回文，而且补得越短越好。第一眼很多人会想到双指针，或者从头到尾试所有前缀是不是回文。思路不算错，就是一提交，长一点的字符串直接超时。

这题我一般先盯住一个地方： 到底哪一段是已经回文的 。因为只能往前面补，所以本质不是“怎么拼”，而是“原串里最长的回文前缀是谁”。只要这个前缀找到了，后半截没进回文的部分反过来贴到前面就完了。

比如：

s = "aacecaaa"

它的最长回文前缀其实就是 "aacecaa" ，剩下一个 "a" 没进去，那答案就是前面补一个 "a" ：

"aaacecaaa"

再看这个：

s = "abcd"

最长回文前缀只有 "a" ，那就把后面的 "bcd" 反过来放前面：

"dcbabcd"

很多人会先这么写：

defshortest_palindrome(s: str) -> str:
defis_pal(sub: str) -> bool:
return sub == sub[::-1]


for i in range(len(s), -1, -1):
if is_pal(s[:i]):
return s[i:][::-1] + s
return s

这代码挺直，逻辑也没毛病。问题在于它一直切片、一直判回文，最坏情况接近 O(n^2) 。字符串一长，这种写法就开始冒汗了。

这题更稳的做法，是拿 KMP 前缀表 来找“最长回文前缀”。

做法不复杂，关键是这个拼接：

t = s + "#" + s[::-1]

为什么这么拼？因为我们想找的是： s 的前缀，和 s[::-1] 的后缀，最长能对齐多少。这个长度，恰好就是原串的最长回文前缀长度。

代码我给一版能直接交的：

defshortest_palindrome(s: str) -> str:
ifnot s:
return s

t = s + "#" + s[::-1]
lps = [0] * len(t)

j = 0
for i in range(1, len(t)):
while j > 0 and t[i] != t[j]:
j = lps[j - 1]
if t[i] == t[j]:
j += 1
lps[i] = j

pal_prefix_len = lps[-1]
suffix = s[pal_prefix_len:]
return suffix[::-1] + s