hiho-2

这两天作死没有干实验室的活，看了两篇Hiho的算法。

KMP 对模式串自己进行构造
最长回文子串 O(N)的Manacher算法
类型转换的特例：同级别的unsigned和signed
KMP
KMP的算法的核心就是，当orig[x] != pattern[i]的时候，找到
1
K = max{k|str(1~k) == str(i-k, i -1)}

这样构成next[i] = K，然后我们就对pattern[next[i] + 1]和orig[x]进行重新判断。这样，复杂度从O(N*M)降到O(M+N)，构建Next数组，本身就是KMP的思想。
以前记得笔记KMP算法。但是好像今天才真正的实现
了一次正确的代码。

Manacher算法-最长回文子串

我感觉hiho网站上并没有说的太清楚。Manacher算法-O(N)挺好理解的。
实际上，求出最长回文子串，如果用BF方法，是O(N^3)。然后借助DP数组或者按照回文子串中心遍历，仍然是O(N^2)。其中的问题是把每个字母当成回文子串，每次都要从1为半径开始比较。
建立一个数组radius[i],记录以i为中心的最长半径回文子串。假设现在以i为中心，然后已经判断的回文子串，在最右边是MaxId,对应的中心是id。那么i关于id的对称点是2id -1. 如果i + radius[2id - 1] < maxId，那么，这个i的半径也就是radius[2*id -1]。因为id为半径的回文子串包括i的子串。不用比较就知道下面不一样了。如果是大于maxId，那么就从maxId开始比较吧。当然，maxId跟id都要更新为i对应的数据。

转换特例

首先看一段代码:

int main() {
	string str = "123";
	int i = -1;
	int len = str.size();
	cout << (i < str.size()) << endl;
	cout << (i < len) << endl;
}

本来以为结果是1 1，但是实际上是1 0.这是因为第一个比较的时候，把i promote 到unsigned int, 然后i是-1，提升后立刻变成了极大的unsigned int值。
具体可以参照：类型转换和类型安全（现代 C++）。其中几句话说的特别好：

编译器不警告有符号和无符号整数类型之间的隐式转换。因此，建议您避免有符号和无符号之间的转换。如果您不能避免它们，然后在您的代码添加运行时检查，以检测选定转换值是否大于等于零或小于等于有符号类型的最大值。此范围内的值将从有符号数传输到无符号数或从无符号数传输到有符号数，而不必经过重新解释。

2016-12-25