Felix021

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），但是却要多加一个分支，所以上面的代码就不改了。

WEB开发有各种复杂性，典型的是HTTP的无状态连接，加密什么的，最近碰到的另一个头疼的事情就是如何获取客户端的真实IP。

其实以前在开发WOJ-Land的时候就遇到这个问题了：如果用户使用了HTTP代理来访问的话，通过REMOTE_ADDR只能获取到HTTP代理的IP，当时只是简单地再判断是否有X-FORWARDED-FOR这个HTTP头（对应PHP的$_SERVER['HTTP_X_FORWARDED_FOR']）来获取客户端的IP。虽然基本达到要求，但是还有各种问题。

一个比较常见的问题就是，如果用户通过多层HTTP代理来访问，那么每个代理都会把自己的IP加到X-FORWARDED-FOR这个头里面（用逗号隔开），真实的浏览器端IP应该是列表的第一个IP。

另外，有些CDN或者其他类似代理的服务，会提供其他的HTTP头，比如 Cdn_Src_Ip，Proxy-Client-IP，WL-Proxy-Client-IP, Client-IP等等。

一个比较合适的做法大概应该是这样：
p.s. 以上代码未经实际运行，可能存在语法问题。

昨天闲着蛋疼，白天把机器挂着下了个Win8开发者预览版，然后从公司远程到家里，UltraISO挂载，点击Setup，点了几个按钮，最后点了个Install，以为会让我选择安装在哪个分区然后再拷贝文件，没想到直接重启把Win7覆盖了，晚上回家一看，丫的已经安装好了，只差我创建帐号再点几个个人配置了。

进入系统以后发现不太习惯。默认进入的是Metro界面，按Windows键或者点击上面的Desktop区域返回桌面；传统的开始菜单貌似完全消失了，按Windows键只是在Metro和传统界面之间切换。Win7的应用都能安装（包括Chrome、QQ、迅雷、Flash插件），但是QQ的聊天窗口不能响应点击事件。此外就是不够稳定，会出现重启/注销卡死的情况，只能长按电源键。Metro界面提供了一些简单的APP，包括五子棋、Piano、Paint等等（其实Piano做的还不错）。可惜没有触摸设备，用鼠标点还是不太给力。

还好上周把Win7 Ghost了一份，截了图就换回Win7了，下面就贴些图吧：

通过Coolshell.cn的这篇文章看了一些东西，简单记下来，方便以后查询。

Tagged: 从简单的15台LAMP服务器发展到现在的1000台服务器，首先采用PHP、单数据库，以实现快速迭代开发；加入memcached大幅缓解数据库压力；使用多台数据库服务器（主从？）扩展处理能力；引入Lucene（Java），提供搜索服务（这个PHP没法做）；数据库压力还是太大，采用Oracle的Sharded Database横向扩展处理能力，同时因为大量的数据库请求，php的短连接不合适，加入了一个中间层。于是整个架构中的各种大压力环节可以简单地使用增加机器的方式来横向扩展，让开发人员可以专注于功能(feature)的开发，而不是焦头烂额地处理各种问题。CTO貌似曾经被Java1.0坑过，有点反感，但是在使用Lucene以后发现，引入Java，使得开发很多类型的功能变得可能（尤其是这些事情对于php不合适，"impractical"），比如利用大量常驻内存的数据来构造关系网、个性化搜索建议等。

Flipkart: （不知道为什么在Load Balancer一节专门提到Apache Thrift） 使用HAProxy和四层设备来进行负载均衡。HAProxy提供RoundRobin和基于IP的两种算法实现负载均衡，支持在4层或者7层进行转发（甚至可以用来搞MySQL），支持高并发，并且能够进行服务器健康检测，总的来说是各方面都比较均衡的解决方案。使用Varnish来实现HTTP缓存，据说效率比Squid要高好几倍，主要是因为将swap的事情交给操作系统来完成。最外面还加了一层nginx，它对js等静态小文件的效率效率非常的高，而且也支持多种负载均衡的协议（不明白为什么要搞好几层负载均衡）。在负载均衡环节，同一个session（一个用户的连续多次请求）不一定落在一个机器上，但是保证落在一组机器，而不是任意一台机器上（三种方案各有优劣，均衡考虑，但是实现复杂性也增加了）。使用heartbeat来保证单点服务的高可用性。使用php-fpm。fk-w3-agent: 运行于每一台web机器上的小型的java daemon，实现php本身不适合完成的异步log、连接池、多线程等、(准)实时配置更新和部署、运行时数据统计。"There are only two hard things in computer science: cache invalidation and naming things."

Beyond PHP: php没能做到的，很多杂碎和坑，可以看看。

用了一段时间的微信，有一些语音消息，想导出来到电脑上，但是全都是aud扩展名的，没有找到可以用的播放器（QuickTime和Foobar2000都搞不定），格式转换也不行（aud2wav, audacity），估计这个"aud"是另一种"aud"，给微信团队发了消息，木有得到回复，只好自己动手。

真的是动手噢……前一阵买的Edifier M178配有一根公对公的音频线，正好可以用来做LineIn。可是LineIn接口在后面，所以干脆插到前置的Mic口上面（其实我很好奇LineIn和Mic口是不是真的有区别），然后打开GoldWave把声音一段一段录下来。好在这种东西没啥音质可言，能录下来就行。

owali.

rsync是个好东西，同步文件很方便，等啥时候有空了，可以考虑把内核提供的inotify功能结合起来，搞一个实时文件同步的应用 :D

回归主题，说说这个坑，线上的机器用rsync来进行文件的同步。


从昨天到今天这个问题一直出现，不管是2.6.8还是最新的3.0.8，看了N个使用例子，最后结果都是这样。Boluor同学的建议是配置信任关系（ssh-keygen -t rsa; ssh-copy-id user@remote_host），但是这样只是不需要输入密码，并没有解决问题。

于是RTFW，Google了一下，发现在 http://ss64.com/bash/rsync.html 的DIAGNOSTIC 一节有说明， .bashrc 等启动脚本的任何输出，都会影响rsync通过ssh同步时的数据流，导致协议不匹配。

以这个命令为例：

$ ssh user@remote_host /bin/true > out.txt

实际上所有的动作是

1.  ssh 与 remote_host 的 sshd 交互
2. sshd fork出一个 user shell(一般是/bin/bash)
3. /bin/bash 载入 $USER/.bash_profile
4. .bash_profile一般会载入.bashrc
5. /bin/bash 执行/bin/true 并重定向stdin到out.txt

正常情况下，out.txt应该是一个空文件。如果在这个过程中有任何输出（比如我当时的.bashrc有一个echo），就会导致rsync在执行过程中的数据有额外的GARBAGE，出现问题。

OVER.

换到VPS以后，悲摧地发现，一旦我访问 felix021.com/test 或者 test.bin(用来下载测带宽) 或者 tst 甚至 ts 都会被BAN。

使用各种方法来排除原因：

1. niginx.conf 里面没有任何关于ban ip的设置
2. 使用apache，情况复现
3. denyhosts里面只配置了ssh的rule
4. 换了8080或者8081端口就不会被BAN
5. 仅仅是80端口被ban（使用nc -v测试，一旦connect成功，立即被断开），而ssh链接等其他端口的应用不受影响
6. 发mail问了VPS提供商，告知没有任何此类限制(曾经在meyu.net 禁止访问 xxx/ip，防灰鸽子)
7. 换了个VPS/IP情况依旧
8. 换了个域名，情况正常。
9. 番羽土啬以后一切正常。

于是突然想起，在使用Godaddy主机的时候，用twitter比较多，觉得总是番羽土啬比较不爽，而且官网图片什么的都不好使，所以曾经在 felix021.com/t 放了个twitese……

于是本域名荣幸地晋级GFW黑名单，特发此文庆贺。

p.s. 本站备用域名 http://tuidaota.com ，目前没有被土啬女干的迹象。

世界上最遥远的距离不是生与死，而是电信和网通之间的距离。

最近晚上都会玩会儿游戏，但是家里是网通的宽带，延迟很大，有时甚至直接提示无法连接服务器，略囧。

为了能够比较顺畅地玩游戏，以前曾经用过“迅雷网游加速器”和“99sushe网游加速器”这两个软件。

以前两款都是收费的，但是都有免费的3~7天试用期。用上以后，可以明显感觉到延迟变小，游戏可玩性增强，只是免费试用期比较短，用了几天以后必须换个账号才行，很麻烦。

不过最近迅雷网游加速器居然永久免费了，毕竟是马上要上市的公司，财大气粗。。

有网游需求的各位同学，推荐试试： http://jsq.xunlei.com

-----

p.s. 写本文的主要目的是参加“写博客，免费得加速器VIP”活动，最多可以送一年，有兴趣的同学也别错过机会……

鉴于本博客是技术博客，简单扯两句。。网游加速器的原理和主要模型其实很简单。

以开头那句话为例，游戏客户端A@网通，网游服务器B@电信，可知A-B之间的延迟通常大得离谱。

于是，搞一台有双网卡的机器X，分别接入电信和网通的线路（这样可以使得 A-X 和 X-B 之间的延迟都很小），并且用iptables之类的东西，配置来自不同网卡的数据包的走向，这样就可以搭好两个网络之间的一座桥。在客户端A，可以使用hook技术拦截游戏发出的数据包，将其处理以后发给这台X，由X将数据包发给游戏服务器B(本来是A->B, 现在变成A->X->B)，然后B返回的数据包由X转给A(B->X->A)，这样就能够使得A-B之间的通信延迟大幅降低。

但是在具体实施上还会遇到很多问题，比如

1. 一台服务器显然不够全国这么多玩家使用，于是需要设置多台服务器。

2. 并不是所有A和X之间的延迟都一样，应该使用ping（icmp）来选择延迟最小的。但是要同时考虑到负载均衡的问题，一台服务器不能连入太多客户端。

3. 从效益上考虑，一台服务器应该尽可能多地承载客户端，这时需要改进技术，比如使用epoll/kqueue来替换传统的select/poll。并且，有些游戏对延迟要求高，有些要求低，可以在一定程度上优化服务器的处理方式。

4. 在用户的机器上，需要对不同的网游客户端进行优化，有些客户端可能会防外挂（这里可能涉及到运营的策略）。还要考虑防火墙的穿透问题。

5. 全国有各种大大小小的运营商，电信网通教育网移动这些是大的，各个地方还会有很多小的运营商，需要增加各种服务器。

6. 。。。。

好了，字数很够了，就废话这么多吧。