朴素的字符串查找的复杂度是 O(MN) 的，显然这里有很大的优化空间，KMP 算法 (Knuth-Morris-Pratt) 可优化至 O(M+N)。

引入 next[]

注：本文使用 Python 的 slice，即 [b:e] 为左闭右开

假设比较如下字符串（上行为 S，下行为 W）

当发现 ‘D’ 与 ‘X’ 不符时，并不需要重新比较 ‘BCABX……’ 和 ‘ABCABD……’ ，而是根据 W 本身的性质，紧接着比较 ‘X……’ 和 ‘CABD……’

可视为在匹配 S 的 ‘X’ 时，比较的字符从 ‘D’(W[5]) “跳至” ‘C’(W[2])
之所以可以这样比较，是因 为 W[0:2] == W[3:5] == ‘AB’

对于 W 中的所有字符，都有这样的允许“跳至”的位置，不妨记录至 next[]数组，例如对于上例的 W，next[5] = 2

参考上文，对于 W，我们这样定义 next[] 数组

1

next[i] = max{j | W[0:j] == W[i-j:i] for -1 <= j < i}

shell 通过修改 .bashrc 可以定制 alias，cmd 则稍稍麻烦一些

cmd 中用 doskey 定义宏，可以直接定义或读取配置文件：

1
2
3

doskey ls=dir
doskey c++11=g++ -std=c++11 $*   :: $*接收剩余的参数
doskey /macrofile=file   :: 或者将 ls=dir 等记录在 file 文件

剩下的问题在于如何让 cmd 自动执行 doskey 指令

shell 默认从 .bashrc 中读取设置，而在 cmd 中需要用 AutoRun 专门指定

假设 C:\alias.doskey 里记录好宏定义，则将下文保存为 reg 文件并运行即可

1
2
3
4

Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Software\Microsoft\Command Processor]
"AutoRun"="doskey /macrofile=C:\\alias.doskey"

Python 调用 Shell 使用 subprocess 即可

（注意: 依照官方文档，使用 subprocess 替换 os.system, os.spawn*, os.popen*, popen2.*, commands.*）

但直接执行 .bashrc 里的命令并不成功，原因没有显示指出需要读取配置

bash 中的读取指令为：

1

/bin/bash -i -c

如下为正确处理方式：

例如 .bashrc 里有 alias saverm=rm -i

1
2
3
4
5

import subprocess as sp
sp.call("/bin/bash -i -c saverm ./", shell=True)
# or use Popen
# p = sp.Popen(["/bin/bash", "-i", "-c", "saverm ./"])
# p.communicate()

简要说明一下，call 其实是封装了 Popen，是同步的（等待子进程完成），
可参考Vamei 的博客

注意：暴露 shell 是相当危险的，比如在 web 下暴露可能被执行 rm 指令

参考并特别感谢 stackoverflow 的解答

Linux 的 tar 并不保存编码集，有如下解决方式：

使用 7zip 或 rar

7zip 安装如无权限，修改 install.sh 里的 DEST_HOME

1

DEST_HOME=~/.local

注：可参考笔者上篇博文

人工/脚本转换文件名

文件内容并不会乱码，因而临时人工修改，或用脚本做映射也是权宜之计

参考:
观夏 Note
浆糊的 BLOG

Linux 软件常常默认安装在 /usr/bin 之类的目录下，没有权限的话需要指定安装路径

通常有以下三种途径：

配置时指定

最常见，如 nginx

1

./configure --prefix=~/.local

注: ./configure 其实是 shell 脚本，根据环境生成 Makefile 或其他

安装时指定

如 Python 的包

1

python setup.py --prefix=~/.local

修改安装的 shell 脚本

如 7zip ，修改 install.sh

1

DEST_HOME=~/.local