Oct
30
比赛的起因是这样的，@Tranch同学在SegmentFault.com提了个问题，求一个代码，可以列出字符串"qwerty"被 "." 分割的所有情况，比如 q.werty qwe.rty q.w.e.r.t.y 等等。
这个问题其实很简单，qwerty中间最多可以塞5个". "，每个地方用1表示塞，0表示不塞，也就是正好循环 2^5 次就行了（对于全0的情况不做特别要求，可有可无），实现起来也非常容易，这里是写这篇文章时补充的一个C语言实现：
不过当时没想写这样的代码，而是特意脑抽用python写了个递归的版本:
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器，于是一时兴起，简化成了这个等价但是更难读的版本：
虽然已经很短了，但是我还是想知道，是否有更简单些的实现（一定程度上可以忽略效率和可读性），于是在MSTC的群里发了这个问题，简单起见，把字符串改成了"abcde"，问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来，被喷“能不能用人话”。这段代码看起来是有些费解，主要思路是，生成 ['****', '***.', '**..', '*...', '....'] 的各种排列，然后用zip('abcd', p)交错组合起来（再删掉'*'）：
然后 @霄妹纸 说，实际上那个是笛卡尔积。于是用上itertools.product，再改善下语法，可以写成这样，看起来就清晰多了：
@霄妹纸 还给出了另外两个奇葩的代码，一个是 C 的，充分利用和宏、main函数的参数和递归：
另一个是ruby的:
由于不懂ruby语法，所以这个代码我也只能勉强看看，不过思路上跟上面的python代码是一样的，使用笛卡尔积生成组合序列，然后再与'abcde'交错组合。
结果是，ruby赢了（58个字节），python紧随其后（80字节，不包括import），C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义，不过可以对比下，不同的语言（C/Ruby/Python）、不同的编程范型（过程式/函数式）的表达方式，一窥函数式编程的魅力～
这个问题其实很简单，qwerty中间最多可以塞5个". "，每个地方用1表示塞，0表示不塞，也就是正好循环 2^5 次就行了（对于全0的情况不做特别要求，可有可无），实现起来也非常容易，这里是写这篇文章时补充的一个C语言实现：
#include <stdio.h>
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
不过当时没想写这样的代码，而是特意脑抽用python写了个递归的版本:
def add_dots_l(str):
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器，于是一时兴起，简化成了这个等价但是更难读的版本：
def add_dots(s):
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
虽然已经很短了，但是我还是想知道，是否有更简单些的实现（一定程度上可以忽略效率和可读性），于是在MSTC的群里发了这个问题，简单起见，把字符串改成了"abcde"，问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来，被喷“能不能用人话”。这段代码看起来是有些费解，主要思路是，生成 ['****', '***.', '**..', '*...', '....'] 的各种排列，然后用zip('abcd', p)交错组合起来（再删掉'*'）：
from itertools import permutations as p #itertools.permutations是python2.6引入的
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
然后 @霄妹纸 说，实际上那个是笛卡尔积。于是用上itertools.product，再改善下语法，可以写成这样，看起来就清晰多了：
from itertools import product #itertools.product也是2.6引入的
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
@霄妹纸 还给出了另外两个奇葩的代码，一个是 C 的，充分利用和宏、main函数的参数和递归：
#define z(a,b) printf(#a"%s",(x>>b)&1?".":""),
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
另一个是ruby的:
p ("b".."e").inject(["a"]){|a,q|a.product [q,"."+q]}.map &:join
如果是ruby 1.9+的话，还可以再少几个字符：p (?b..?e).inject([?a]){|a,q|a.product [q,?.+q]}.map&:join
由于不懂ruby语法，所以这个代码我也只能勉强看看，不过思路上跟上面的python代码是一样的，使用笛卡尔积生成组合序列，然后再与'abcde'交错组合。
结果是，ruby赢了（58个字节），python紧随其后（80字节，不包括import），C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义，不过可以对比下，不同的语言（C/Ruby/Python）、不同的编程范型（过程式/函数式）的表达方式，一窥函数式编程的魅力～
Jun
30
这是2012年百度实习招聘非技术类的某道笔试题。
给一个5×5的矩阵，每个元素只能是0或者1。
请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？
==== 分割线 ====
乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。
然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。
最简单的做法就是
一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。
更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。
再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。
到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
(p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）
于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。
==== 分割线 ====
扩展：
1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？
根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。
2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)
这个结论就不那么直接了，对M*N有一定的限制。
给一个5×5的矩阵，每个元素只能是0或者1。
请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？
==== 分割线 ====
乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。
然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。
最简单的做法就是
for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++;
这个check_even(i)里头把 i 当成一个25bit的二进制数字，并转换为对应的5*5矩阵，判断其每一行和每一列是否满足要求。（p.s. whusnoopy的做法是直接使用位运算，更简单，不过思路就断了。。）一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。
更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。
再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。
到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
(p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）
于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。
==== 分割线 ====
扩展：
1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？
根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。
2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)
这个结论就不那么直接了，对M*N有一定的限制。
May
20
从哪儿说起呢？我想了想，从 gets 说起可能最好。
初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……
或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。
这就是典型的溢出攻击。
为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。
这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。
加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。
strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
比较诡异的两件事情是：
1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符
2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充
以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。
事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。
众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。
参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……
或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。
这就是典型的溢出攻击。
为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。
这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。
加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。
strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
char* strncpy(char *dest, const char *src, size_t n){
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[i] = src[i];
for ( ; i < n ; i++)
dest[i] = '\0';
return dest;
}
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[i] = src[i];
for ( ; i < n ; i++)
dest[i] = '\0';
return dest;
}
比较诡异的两件事情是：
1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符
2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充
以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。
事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。
众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
strncpy(inode->d_name, filename, 14);
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
snprintf(dest, n, "%s", src);//注意，不能直接用src来替换"%s"
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。
参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
Apr
8
翻译自：How To Read C Declarations 英文原文
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……
就算是非常有经验的C程序员，也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说，下面这个是一个指针的数组，还是一个数组的指针？
下面这货到底是什么？
当然了，这货是一个指针，指向一个数组，这个数组的每个元素是一个指针，指向一个函数，函数的返回值类型是int :)
这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇，但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的（尽管我总会被计算机语言结构和神秘的事物搞得很兴奋）。然而我的确记得，能够写出一个程序，将任何声明转换成英语。
== 黄金法则 ==
这个法则是这样说的：
最简单的情况是这样的：
从 i 开始，你向右看，啥都没看到；然后就向左看，看到了int，说出来：i是一个int。
然后看个复杂一点的：
从 a 开始：向右看，说“是一个包含3个元素的数组”；向左看，说“数组的每个元素是指针”；向右看，啥都没；向左看，说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组，每个元素是一个指针，指向int。
加上一对括号让它看起来更怪异点儿：
像在普通表达式中一样，括号改变了阅读/计算的顺序。从 a 开始：向右看，遇到括号了，往回；向左看，说“是一个指针”，遇到(括号，跳出来；向右看，[3]，说“指向一个包含3个元素的数组”；向左看，int，说“数组的每个元素是int”。综合起来：a是一个指针，指向一个包含3个元素的数组，数组的每个元素是一个int。
好，再来看看这个：
赞，你说：foo是一个函数，返回一个指针，指向int。
接下来跳一步：就像我们可以定义一个指向int的指针，我们也可以定义一个指向函数的指针。在这种情况下，不需要extern了（因为不是函数的前向引用声明），而是一个变量的定义。这是一个基本的函数指针：
从foo开始：向右看，遇到括号，往回；向左看，*，说“是一个指针”，遇到左括号，跳出来；向右看，()，说“指向一个函数”；向左看，int，说“函数返回int”。综合起来：foo是一个指针，指向一个函数，函数返回int。
下面是一个数组，每个元素是一个指针，指向函数，函数返回int：
你还需要最后一个，诡异的难以置信的声明：
这是一个指针，指向一个数组，数组的每个元素是个指针，指向一个函数，函数的返回值是int。发现了吗？这货就是上面那个object_vtable的指针，也就是你定义的每一个对象需要的虚函数表(vtable)的指针。
这个指向vtable的指针是一个vtable的地址，例如，&Truck_vtable （就是某个Truck类的实例虚函数表的指针）。
== 总结 ==
接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形（就像最初的C Front - C++转C翻译器）。
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……
就算是非常有经验的C程序员，也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说，下面这个是一个指针的数组，还是一个数组的指针？
int *a[10];
下面这货到底是什么？
int (*(*vtable)[])();
当然了，这货是一个指针，指向一个数组，这个数组的每个元素是一个指针，指向一个函数，函数的返回值类型是int :)
这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇，但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的（尽管我总会被计算机语言结构和神秘的事物搞得很兴奋）。然而我的确记得，能够写出一个程序，将任何声明转换成英语。
== 黄金法则 ==
这个法则是这样说的：
引用
从标识符开始（或者最内层的结构，如果不存在标识符的话，通常出现于函数指针），首先向右看，直到遇到 ) 括号或者结束，看到什么就说出来；然后向左看，直到遇到 ( 括号或者回到行首，看到什么就说出来。跳出一层括号，重复上述过程：右看看，说出来；左看看，说出来。直到你说出变量的类型或者返回值（针对函数指针），也就表示你把声明都读完了。
最简单的情况是这样的：
int i;
从 i 开始，你向右看，啥都没看到；然后就向左看，看到了int，说出来：i是一个int。
然后看个复杂一点的：
int *a[3];
从 a 开始：向右看，说“是一个包含3个元素的数组”；向左看，说“数组的每个元素是指针”；向右看，啥都没；向左看，说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组，每个元素是一个指针，指向int。
加上一对括号让它看起来更怪异点儿：
int (*a)[3];
像在普通表达式中一样，括号改变了阅读/计算的顺序。从 a 开始：向右看，遇到括号了，往回；向左看，说“是一个指针”，遇到(括号，跳出来；向右看，[3]，说“指向一个包含3个元素的数组”；向左看，int，说“数组的每个元素是int”。综合起来：a是一个指针，指向一个包含3个元素的数组，数组的每个元素是一个int。
好，再来看看这个：
extern int *foo();
赞，你说：foo是一个函数，返回一个指针，指向int。
接下来跳一步：就像我们可以定义一个指向int的指针，我们也可以定义一个指向函数的指针。在这种情况下，不需要extern了（因为不是函数的前向引用声明），而是一个变量的定义。这是一个基本的函数指针：
int (*foo)();
从foo开始：向右看，遇到括号，往回；向左看，*，说“是一个指针”，遇到左括号，跳出来；向右看，()，说“指向一个函数”；向左看，int，说“函数返回int”。综合起来：foo是一个指针，指向一个函数，函数返回int。
下面是一个数组，每个元素是一个指针，指向函数，函数返回int：
int (*Object_vtable[])();
你还需要最后一个，诡异的难以置信的声明：
int (*(*vtable)[])();
这是一个指针，指向一个数组，数组的每个元素是个指针，指向一个函数，函数的返回值是int。发现了吗？这货就是上面那个object_vtable的指针，也就是你定义的每一个对象需要的虚函数表(vtable)的指针。
这个指向vtable的指针是一个vtable的地址，例如，&Truck_vtable （就是某个Truck类的实例虚函数表的指针）。
== 总结 ==
接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形（就像最初的C Front - C++转C翻译器）。
int *ptr_to_int;
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
Jan
12
对于没有GC的语言来说，这实在是最让人头疼的事情了，毕竟内存泄漏是最难处理的问题（之一?），对于一个后台server，即使只是一个小小的泄漏，日积月累，也会导致灾难性的后果。有个传闻说的是，某公司的某下载软件的某后台server，由于有个无法定位的内存泄漏问题，导致服务的内存占用不断增加，以至于只能每隔一段时间重启之。
有人说，C/C++程序员有一半的工作量是花在处理内存泄漏上面，但是很遗憾，内存泄漏仍然屡见不鲜。一旦出现泄漏，能做的事情不多，上述处理方式是消极做法之一，有效，但治标不治本。积极一点的，也不外乎这两个：一是看代码，反复看代码，请别人看代码，请别人反复看代码；或是借助valgrind之类的工具来跟踪内存的分配/释放（而且并不适用于所有程序，例如某些程序寄希望于在其终止时让OS来释放那些只需申请一次且无需释放的内存）。一些额外的测试工作也许能帮助缩小查看代码的范围，但也只能这样了。
既是如此，在程序运行之前，就应该先把好关。
对于C语言，这确实是个比较痛苦的事情。毕竟C语言只是汇编的高级语言封装，语言本身提供的能力很有限。
假定有一个函数申请了多次内存，那么每次遇到错误需要退出的时候，为了避免内存泄漏，必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序：
于是万恶的goto出场了。为了解决上面的问题，引入goto可以使得每个资源只需要写一份对应的释放代码，例如： 什么意思呢？假定在第一步，给 a 分配内存的时候失败了，那么还没来得及去定义 b 并给其初始化赋值，就跳转到了wtf这儿，而在wtf下面的第二行，却引用了 b 这个变量，对于编译器而言，这便无法处理了。正确的代码应该是：
对变量就近定义的好坏见仁见智了，但是goto毕竟不是个好东西，所以看过内核代码的同学可能会发现另外一种替代性的结构：do-while(0) 。乍一看这个结构似乎没有意义，有点奇怪，但是却很好用，很适合用来消除goto语句，例如上面的代码可以这么做：
但是do-while(0)和goto一样，不是万金油，对于很多较复杂的情况也不能很好的解决，甚至会使得程序更加晦涩难懂。对于do-while(0)，如果在这个结构内还有一个循环，循环里面出错想要跳出do-while(0)，break就不奏效了（至于为什么，你懂的），这时代码怎么写都恶心，只能羡慕Java里面的break label语法了；而对于比较复杂的资源，比如上文中申请到的内存是 a->b->c 这样嵌套的，那么如何安排内存释放代码，又要让人头疼了。合理的使用goto/do-while(0)，将过长的代码拆分成多个函数等都可以起到一定的帮助。
只是很可惜，C语言的能力大概就只能走到这里了。想走得更远，就得借助C++来完成了。虽然C++没有gc，但是由于其OO的特性，使得RAII的实现变得可能。
所谓RAII，即 Resource Acquizition Is Initialization。很晦涩吧？其实具体实现很简单：把资源封装成一个类，在其构造函数中分配，在析构函数中释放。当需要使用的时候，在栈上初始化一个对象，当这个对象生命周期结束的时候，其析构函数会被调用，自动完成资源的释放。对于前面提到的例子，可以把A/B/C封装成一个class，对应的a/b/c就是实例化得到的三个对象，当func函数结束的时候，abc对应的内存就会被释放。同样的方法也适用于锁、互斥量、文件指针等其他类型的资源。下面这段代码以pthread_mutex为例，演示了RAII的使用:
不过程序中因为各种原因常需要使用 new 来分配资源（内存、对象等），这样对应的指针还是得在其生命周期结束的时候被释放，总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器，实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr（但是必须是使用new获得的，特别注意：new[]分配的不行），auto_ptr对象将ptr包装起来，并重载了 * 和 -> 两个操作符，使得该对象能像指针一样被使用，并且在该对象被生命周期的时候，其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用：
既然说到auto_ptr，为什么不用它来写例子呢？因为auto_ptr的某些特性导致其有大坑，在很多地方不受待见，以至于在 c++11 标准里，auto_ptr被废弃了，因此不建议在项目中使用它了。有兴趣的同学可以去翻看《C++标准程序库》对auto_ptr的介绍。
本来计划写到这里要告一段落了，但是上面的 x_ptr 有坑，无奈只好继续……为什么说有坑呢？举两个例子：
针对func1的问题，可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝，代码如下
而针对func2的问题，解决方法呢，要么是写一个x_ptr_arr，使用delete[]来处理；要么是在x_ptr的构造函数里加一个flag，用来指定是否是new[]分配的，当然，为了方便，可以设置一个默认值false.....
补充一句，这里的x_ptr其实是boost::scoped_ptr的缩水版了，有兴趣的同学可以自行Google了解更多，关于内存泄漏的话题，这篇大概就说这么多了吧。
最后，感谢Sandy同学的 C++中利用RAII在stack上管理资源I ，本篇有多处参考该文。希望他能抽出时间把 II 给写完吧 :P
有人说，C/C++程序员有一半的工作量是花在处理内存泄漏上面，但是很遗憾，内存泄漏仍然屡见不鲜。一旦出现泄漏，能做的事情不多，上述处理方式是消极做法之一，有效，但治标不治本。积极一点的，也不外乎这两个：一是看代码，反复看代码，请别人看代码，请别人反复看代码；或是借助valgrind之类的工具来跟踪内存的分配/释放（而且并不适用于所有程序，例如某些程序寄希望于在其终止时让OS来释放那些只需申请一次且无需释放的内存）。一些额外的测试工作也许能帮助缩小查看代码的范围，但也只能这样了。
既是如此，在程序运行之前，就应该先把好关。
对于C语言，这确实是个比较痛苦的事情。毕竟C语言只是汇编的高级语言封装，语言本身提供的能力很有限。
假定有一个函数申请了多次内存，那么每次遇到错误需要退出的时候，为了避免内存泄漏，必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序：
void func(){
void *a = malloc(sizeof(A));
if (NULL == a) {
return;
}
void *b = malloc(sizeof(B));
if (NULL == b) {
free(a);
return;
}
void *c = malloc(sizeof(C));
if (NULL == c) {
free(a);
free(b);
return;
}
......
}
有效，但是不靠谱。当这个函数长达数百行、有多处申请内存的时候，其可维护性是相当低的。当然，使用 alloca 这个非标准的内存分配函数可以在某些情况下解决问题，但是如果申请的内存较大（栈空间不够）、或者分配到的内存被用于较复杂的结构（比如还包含其他资源的指针）、资源不是内存（比如文件指针、锁等同样需要在生命周期结束被释放的资源），alloca就无能为力了。void *a = malloc(sizeof(A));
if (NULL == a) {
return;
}
void *b = malloc(sizeof(B));
if (NULL == b) {
free(a);
return;
}
void *c = malloc(sizeof(C));
if (NULL == c) {
free(a);
free(b);
return;
}
......
}
于是万恶的goto出场了。为了解决上面的问题，引入goto可以使得每个资源只需要写一份对应的释放代码，例如：
void func(){
void *a = malloc(sizeof(A));
if (NULL == a) goto wtf;
void *b = malloc(sizeof(B));
if (NULL == b) goto wtf;
void *c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
看起来很棒对不对？但是实际上并不能通过编译，gcc会提示类似这样的错误：void *a = malloc(sizeof(A));
if (NULL == a) goto wtf;
void *b = malloc(sizeof(B));
if (NULL == b) goto wtf;
void *c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
引用
cross.c:14: error: jump to label ‘wtf’
cross.c:9: error: from here
cross.c:11: error: crosses initialization of ‘void* c’
cross.c:9: error: from here
cross.c:11: error: crosses initialization of ‘void* c’
void func(){
void *a = NULL, *b = NULL, *c = NULL;
a = malloc(sizeof(A));
if (NULL == a) goto wtf;
b = malloc(sizeof(B));
if (NULL == b) goto wtf;
c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
这样一来便要求所有在 goto 之后被用到的变量都必须在第一个goto之前定义，并赋初值。这就类似c89/pascal的做法了，强制要求所有变量在函数的开头定义，失去了变量就近定义的便捷性和一些其他的好处(sandy的说法是“局部性”，但是窃以为变量的就近定义跟局部性关系不大，更多的是在C++中，对象的就近定义可以在一些情况下避免不必要的初始化，并且可能需要之前的一些处理结果）。这儿有个更复杂的例子，作者指出，在驱动/linux内核中大量使用了这种方式来释放资源。注意，稍有不同的是，这个例子有多种资源，函数末尾有多个label，按照资源申请顺序的倒序释放资源（为什么呢，看代码吧～）void *a = NULL, *b = NULL, *c = NULL;
a = malloc(sizeof(A));
if (NULL == a) goto wtf;
b = malloc(sizeof(B));
if (NULL == b) goto wtf;
c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
对变量就近定义的好坏见仁见智了，但是goto毕竟不是个好东西，所以看过内核代码的同学可能会发现另外一种替代性的结构：do-while(0) 。乍一看这个结构似乎没有意义，有点奇怪，但是却很好用，很适合用来消除goto语句，例如上面的代码可以这么做：
void func(){
void *a = NULL, *b = NULL, *c = NULL;
do {
a = malloc(sizeof(A));
if (NULL == a) break;
b = malloc(sizeof(B));
if (NULL == b) break;
c = malloc(sizeof(C));
if (NULL == c) break;
......
} while (0);
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
既消除了“不法分子”，也达到了避免冗余的目的。对于这个结构，其实还有更多的好处，详见这里。void *a = NULL, *b = NULL, *c = NULL;
do {
a = malloc(sizeof(A));
if (NULL == a) break;
b = malloc(sizeof(B));
if (NULL == b) break;
c = malloc(sizeof(C));
if (NULL == c) break;
......
} while (0);
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
但是do-while(0)和goto一样，不是万金油，对于很多较复杂的情况也不能很好的解决，甚至会使得程序更加晦涩难懂。对于do-while(0)，如果在这个结构内还有一个循环，循环里面出错想要跳出do-while(0)，break就不奏效了（至于为什么，你懂的），这时代码怎么写都恶心，只能羡慕Java里面的break label语法了；而对于比较复杂的资源，比如上文中申请到的内存是 a->b->c 这样嵌套的，那么如何安排内存释放代码，又要让人头疼了。合理的使用goto/do-while(0)，将过长的代码拆分成多个函数等都可以起到一定的帮助。
只是很可惜，C语言的能力大概就只能走到这里了。想走得更远，就得借助C++来完成了。虽然C++没有gc，但是由于其OO的特性，使得RAII的实现变得可能。
所谓RAII，即 Resource Acquizition Is Initialization。很晦涩吧？其实具体实现很简单：把资源封装成一个类，在其构造函数中分配，在析构函数中释放。当需要使用的时候，在栈上初始化一个对象，当这个对象生命周期结束的时候，其析构函数会被调用，自动完成资源的释放。对于前面提到的例子，可以把A/B/C封装成一个class，对应的a/b/c就是实例化得到的三个对象，当func函数结束的时候，abc对应的内存就会被释放。同样的方法也适用于锁、互斥量、文件指针等其他类型的资源。下面这段代码以pthread_mutex为例，演示了RAII的使用:
class Mutexer {
private:
pthread_mutex_t *mutex;
public:
Mutexer(pthread_mutex_t *m) { mutex = m; }
~Mutexer() { Unlock(); }
Lock() { pthread_mutex_lock(mutex); }
Unlock() { pthread_mutex_unlock(mutex); }
};
//Global mutex
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void func() {
Mutexer mtx(&mutex);
mtx::lock();
if (sth. failed) {
return;
}
}
private:
pthread_mutex_t *mutex;
public:
Mutexer(pthread_mutex_t *m) { mutex = m; }
~Mutexer() { Unlock(); }
Lock() { pthread_mutex_lock(mutex); }
Unlock() { pthread_mutex_unlock(mutex); }
};
//Global mutex
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void func() {
Mutexer mtx(&mutex);
mtx::lock();
if (sth. failed) {
return;
}
}
不过程序中因为各种原因常需要使用 new 来分配资源（内存、对象等），这样对应的指针还是得在其生命周期结束的时候被释放，总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器，实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr（但是必须是使用new获得的，特别注意：new[]分配的不行），auto_ptr对象将ptr包装起来，并重载了 * 和 -> 两个操作符，使得该对象能像指针一样被使用，并且在该对象被生命周期的时候，其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用：
template <typename T>
class x_ptr
{
private:
T* x;
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; }
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
void func(){
x_ptr<int> p(new int);
*p = 3;
}
代码的最后无需显式调用 delete 需释放分配的那个int，却照样避免了内存的泄漏。class x_ptr
{
private:
T* x;
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; }
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
void func(){
x_ptr<int> p(new int);
*p = 3;
}
既然说到auto_ptr，为什么不用它来写例子呢？因为auto_ptr的某些特性导致其有大坑，在很多地方不受待见，以至于在 c++11 标准里，auto_ptr被废弃了，因此不建议在项目中使用它了。有兴趣的同学可以去翻看《C++标准程序库》对auto_ptr的介绍。
本来计划写到这里要告一段落了，但是上面的 x_ptr 有坑，无奈只好继续……为什么说有坑呢？举两个例子：
void func1() {
x_ptr<int> p(new int), q(new int);
*p = 1;
*q = 2;
p = q;
}
void func2() {
x_ptr<int> p(new int[10]);
}
在 func1 中，由于进行了拷贝（其实拷贝构造也一样），导致 p 对应的那块空间会被泄漏，而 q 对应的那块空间会被释放2次；在 func2 中，x_ptr试图用delete去释放由new[]分配的内存空间，其结果是未定义的（比如不是基本元素而是某个class，程序可能会直接崩溃）。x_ptr<int> p(new int), q(new int);
*p = 1;
*q = 2;
p = q;
}
void func2() {
x_ptr<int> p(new int[10]);
}
针对func1的问题，可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝，代码如下
template <typename T>
class x_ptr
{
private:
T* x;
x_ptr(const x_ptr&);
x_ptr& operator= (const x_ptr& v);
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; };
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
class x_ptr
{
private:
T* x;
x_ptr(const x_ptr&);
x_ptr& operator= (const x_ptr& v);
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; };
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
而针对func2的问题，解决方法呢，要么是写一个x_ptr_arr，使用delete[]来处理；要么是在x_ptr的构造函数里加一个flag，用来指定是否是new[]分配的，当然，为了方便，可以设置一个默认值false.....
补充一句，这里的x_ptr其实是boost::scoped_ptr的缩水版了，有兴趣的同学可以自行Google了解更多，关于内存泄漏的话题，这篇大概就说这么多了吧。
最后，感谢Sandy同学的 C++中利用RAII在stack上管理资源I ，本篇有多处参考该文。希望他能抽出时间把 II 给写完吧 :P
Dec
23
这程序写了好几次了，干脆贴出来吧～附上exe。
下载文件 (已下载 1299 次)
#include <stdio.h>
#include <stdlib.h>
char str[65536];
int main() {
int i;
for (i = 0; i < 65536; i++) str[i] = '1';
str[65535] = '\0';
i = 0;
while (1) {
i++;
if (i % 3000 == 0) {
sleep(1);
}
puts(str);
}
return 0;
}
#include <stdlib.h>
char str[65536];
int main() {
int i;
for (i = 0; i < 65536; i++) str[i] = '1';
str[65535] = '\0';
i = 0;
while (1) {
i++;
if (i % 3000 == 0) {
sleep(1);
}
puts(str);
}
return 0;
}
下载文件 (已下载 1299 次)
Nov
15
@2019-03-19 STL里的lowerbound算法简单有效。
该元素在数组中不一定存在，只是要找一个i，使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
该元素在数组中不一定存在，只是要找一个i，使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e)，左闭右开，类似STL。
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
Oct
13
Translated to ENGLISH VERSION
源于这两篇文章：
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天，终于理解了，在这里记录一下自己的思路，免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。 为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#（注意，下面的代码是用C语言写就，由于C语言规范还要求字符串末尾有一个'\0'所以正好OK，但其他语言可能会导致越界）。
下面以字符串12212321为例，经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：
那么怎么计算P[i]呢？该算法增加两个辅助变量（其实一个就够了，两个更清晰）id和mx，其中 id 为已知的 {右边界最大} 的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界。
然后可以得到一个非常神奇的结论，这个算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点，理解起来会简单很多：
当然光看代码还是不够清晰，还是借助图来理解比较容易。
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。
于是代码如下：
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出，由于 P[id] = mx，所以 S[id-mx] != S[id+mx]，那么当 P[j] > mx - i 的时候，可以肯定 P[i] = mx - i ，不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点，也只是多一次匹配（必然会fail），但是却要多加一个分支，所以上面的代码就不改了。
源于这两篇文章：
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天，终于理解了，在这里记录一下自己的思路，免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。 为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#（注意，下面的代码是用C语言写就，由于C语言规范还要求字符串末尾有一个'\0'所以正好OK，但其他语言可能会导致越界）。
下面以字符串12212321为例，经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）
那么怎么计算P[i]呢？该算法增加两个辅助变量（其实一个就够了，两个更清晰）id和mx，其中 id 为已知的 {右边界最大} 的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界。
然后可以得到一个非常神奇的结论，这个算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点，理解起来会简单很多：
//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。
当然光看代码还是不够清晰，还是借助图来理解比较容易。
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。
于是代码如下：
//输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出，由于 P[id] = mx，所以 S[id-mx] != S[id+mx]，那么当 P[j] > mx - i 的时候，可以肯定 P[i] = mx - i ，不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点，也只是多一次匹配（必然会fail），但是却要多加一个分支，所以上面的代码就不改了。
