算法复健 Day8 - 字符串 LC 151，卡码网 55，LC 28，459

今天字符串专题收尾，前两题是翻转技巧的延伸，后两题正式引入 KMP，难度跳了一个台阶。

LC 151 · 翻转字符串里的单词

思路：先整体反转，再逐词反转。

去掉首尾空格和中间多余空格后，先把整个字符串反转，再对每个单词单独反转，顺序就还原了。经典的"三次翻转"技巧，空间 O(1)（Python 因为字符串不可变实际上做不到，但思路要懂）。

Python 一行流：' '.join(s.split()[::-1])，面试时先把思路说清楚再用这个。

卡码网 55 · 右旋转字符串

思路：同样是三次翻转。

右旋 k 位等价于：先整体反转，再分别反转前 k 个字符和后 n-k 个字符。和 151 换汤不换药，翻转技巧的又一次练习。

LC 28 · 实现 strStr() —— KMP 登场

思路：KMP 算法。

暴力匹配是 O(m*n)，KMP 靠一张 next 数组（前缀表）做到 O(m+n)。

next 数组记录的是模式串每个位置的最长相等前后缀长度，匹配失败时不从头开始，而是查表跳到该跳的位置，避免重复比较。

KMP 的难点全在构建 next 数组——理解"为什么这样跳"比背代码重要，建议手推一遍。代码本身不长，但每次写都要想清楚再动手。

LC 459 · 重复的子字符串

思路：KMP next 数组的性质应用。

如果字符串 s 由某个子串重复构成，那么 s 的最长相等前后缀长度 len(s) – next[-1] 一定能整除 len(s)。直接用 KMP 的 next 数组判断，O(n) 搞定。

还有一个取巧做法：把 s+s 掐头去尾，看原字符串 s 是否还在里面——原理一样，Python 写起来就两行。

今天最大的坎是 KMP，说实话第一次学很容易绕晕，next 数组的构建过程要多画图多手推，理解了"利用已匹配信息避免回退"这个核心思想之后，代码就自然好写了。字符串专题到此收官，下一章见～

明天继续加油！