实现strStr题解补充

补充一下strStr题解的推导过程吧

性质

1. 关于$\pi (i)\le \pi (i-1)+1$

   • 在下文中可能有不严谨的地方在于可能会出现$\pi (i)\le 2$的情况，从而导致出现左区间的右端点比左端点小。右区间的左端点比右端点大，从而形成非法区间。这个时候我们规定这个区间不存在，其对应的值是0即可。

   • 依据 $\pi (i)$定义得： $s[0:\pi (i)-1]=s[i-\pi (i)+1:i]$

     • 关于写法，这个写法有点像python的切片，指的是截取子串，区别在于这是左闭右闭区间，python的是左闭右开
     • 当s[0:i]的真前缀和真后缀相等的长度是$\pi (i)$，那么自然正取$\pi (i)$个字符和逆取$\pi (i)$个字符所形成的两个子串是相等的。

   • 将两区间的右端点同时左移，可得$s[0:\pi (i)-2]=s[i-\pi (i)+1:i-1]$

     • 比方说以题目的$\pi (6)$为例子，aabaaab的最长相等真前后缀是aab。那么当两侧右端点同时左移一定有aa=aa，所以这个是很自然的事情。
     • 根据$\pi (i)$的定义，我们可以很轻松的知道这个将会得到$\pi (i)-1$，因为$\pi (i)$是左右真前后缀相等的长度，两边同时减1，对于整体来说匹配上的长度只减了1

   • 依据 $\pi (i-1)$定义得：$\pi (i-1)\ge \pi (i)-1$，即$\pi (i)\le \pi (i-1)+1$

     • 这个定义就是要证明$s[0:\pi (i)-2]=s[i-\pi (i)+1:i-1]$就是$\pi (i-1)$的下界。$\pi (i-1)$是$s[0:i-1]$的最长相等真前后缀长度，而$s[0:\pi (i)-2]=s[i-\pi (i)+1:i-1]$等式两端显然都在0到i-1范围之内，也就是说不管$s[0:i-1]$是什么样的，都一定可以取到这个值，由此包含是一定的。而不可能会存在更小的下界。
     • 大于号在这种情况下会取得，那就是$s[0:\pi (i)-2+n]=s[i-\pi (i)+1-n:i-1]$，也就是把后缀往前移动n格子，刚好重合，而且$s[\pi (i)-1:\pi (i)-2+n]=s[i-1+1:n]$
     • 更具体的说 比如像 aabaa和aabaaa,前者是i-1的串，后者是i的串，$\pi (i)=2(aa嘛)$，我们看i-1的串，直接砍掉aabaaa最后的a，一定会有的是a=a，这是下界决定的，但是我们可以发现把第五个a往前平移一格就有重合的a，然后s[1]又恰好等于s[4]，所以就超越了下界。