代码随想录算法训练营第九天 | 151.翻转字符串里的单词、卡码网：55.右旋转字符串、28. 实现 strStr()、459.重复的子字符串

151.翻转字符串里的单词

Python因为有切片，做这类题非常简单，这里就仅学习一下Carl网站的C++写法思想。
Python实现：

class Solution:def reverseWords(self, s: str) -> str:return ' '.join(s.split()[::-1])

卡码网：55.右旋转字符串

同上，python实现如下：

import sysdef rhRotation(s, n):return s[-n:] + s[:-n]if __name__=="__main__":n = int(sys.stdin.readline())s = sys.stdin.readline()print(rhRotation(s, n))

28. 实现 strStr()

KMP是今天的主菜。
KMP最关键的在于LPS，LPS记录了模式串当前位置的Longest Prefix Suffix，因此，如果在主字符串的某位置未能匹配，则将模式串回退到LPS位置重新匹配。
CSIT5500的字符串章节已经学过KMP和后缀数组，这题模式串就是needle，先计算needle的next数组，然后匹配时找到一次匹配就退出。
这代码还真不容易写对…

class Solution:def strStr(self, haystack: str, needle: str) -> int:nxt = [-1] * len(needle)q = -1for k in range(1, len(needle)):while q != -1 and needle[q + 1] != needle[k]:q = nxt[q]if needle[q + 1] == needle[k]:q += 1nxt[k] = qq = -1for k in range(len(haystack)):while q != -1 and needle[q + 1] != haystack[k]:q = nxt[q]if needle[q + 1] == haystack[k]:q += 1if q == len(needle) - 1:return k - qreturn -1

459.重复的子字符串

这题当时一刷逃课了，直接

return s in (s + s)[1:-1] if s else False

即可AC。
假如不能用内置方法，kmp可解这题。不需要匹配，直接把s当成模式串，判断模式串的周期性即可。
Trick在于如何判断周期性结构，假如模式串确实是周期性的，LPS[-1]提供的信息已经足够得到周期信息。因为LPS[-1]的意义就是前缀后缀相匹配的最大长度，假如记$pattern=y^r$, $y\in {\Sigma }^{\ast },r>1$，那么LPS[-1]$=y^{r-1}$，于是代码也就简单了，先看是否可能有周期，然后如果有可能有周期，求出可能的周期，看能否被字符串长度整除即可。

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:n = len(s)q = -1nxt = [-1] * nfor k in range(1, n):while q != -1 and s[q + 1] != s[k]:q = nxt[q]if s[q + 1] == s[k]:q += 1nxt[k] = qreturn nxt[-1] != -1 and n % (n - nxt[-1] - 1) == 0