Jansfer@82cs.com

/proc/sys/net/ipv4/icmp_timeexceed_rate
这个在traceroute时导致著名的“Solaris middle star”。这个文件控制发送ICMP Time Exceeded消息的比率。
/proc/sys/net/ipv4/igmp_max_memberships
主机上最多有多少个igmp (多播)套接字进行监听。
/proc/sys/net/ipv4/inet_peer_gc_maxtime
求助: Add a little explanation about the inet peer storage? Minimum interval between garbage collection passes. This interval is in effect under low (or absent) memory pressure on the pool. Measured in jiffies.
/proc/sys/net/ipv4/inet_peer_gc_mintime
每一遍碎片收集之间的最小时间间隔。当内存压力比较大的时候，调整这个间隔很有效。以jiffies计。
/proc/sys/net/ipv4/inet_peer_maxttl
entries的最大生存期。在pool没有内存压力的情况下(比如，pool中entries的数量很少的时候)，未使用的entries经过一段时间就会过期。以jiffies计。
/proc/sys/net/ipv4/inet_peer_minttl
entries的最小生存期。应该不小于汇聚端分片的生存期。当pool的大小不大于inet_peer_threshold时，这个最小生存期必须予以保证。以jiffies计。
/proc/sys/net/ipv4/inet_peer_threshold
The approximate size of the INET peer storage. Starting from this threshold entries will be thrown aggressively. This threshold also determines entries’ time-to-live and time intervals between garbage collection passes. More entries, less time-to-live, less GC interval.
/proc/sys/net/ipv4/ip_autoconfig
这个文件里面写着一个数字，表示主机是否通过RARP、BOOTP、DHCP或者其它机制取得其IP配置。否则就是0。
/proc/sys/net/ipv4/ip_default_ttl
数据包的生存期。设置为64是安全的。如果你的网络规模巨大就提高这个值。不要因为好玩而这么做——那样会产生有害的路由环路。实际上，在很多情况下你要考虑能否减小这个值。
/proc/sys/net/ipv4/ip_dynaddr/proc/sys/net/ipv4/icmp_destunreach_rate

现象:在netstat的时候发现大量处于LAST_ACK状态的TCP连接，达到在ESTABLISHED状态的90%以上 [root@ccsafe ~]# netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c                 
       6 CLOSE_WAIT
       7 CLOSING      
    6838 ESTABLISHED
    1037 FIN_WAIT1   
     357 FIN_WAIT2   
    5830 LAST_ACK     
       2 LISTEN      
     276 SYN_RECV     
      71 TIME_WAIT   
[root@ccsafe ~]#
看看系统 状态，性能 都花在系统中断和上下文切换
[root@ccsafe ~]# vmstat 2
procs ———–memory———- —swap– —–io—- –system– —–cpu——
r b    swpd    free    buff cache     si    so     bi     bo    in    cs us sy id wa st
1 0       0 3091812 363032 284132     0     0      0      0     1     1 0 0 100 0 0
0 0       0 3091812 363032 284132     0     0      0      0 13750 3174 0 5 94 0 0
0 0       0 3091936 363032 284132     0     0      0      0 13666 3057 1 5 94 0 0
0 0       0 3092060 363032 284132     0     0      0     16 13749 3030 0 5 95 0 0
0 0       0 3092060 363032 284132     0     0      0      0 13822 3144 0 5 95 0 0
0 0       0 3092060 363032 284132     0     0      0      0 13390 2961 0 5 95 0 0
0 0       0 3092060 363032 284132     0     0      0      0 13541 3182 0 6 94 0 0
查看socket队列信息
[root@ccsafe ~]# sar -n SOCK 5
Linux 2.6.18-53.1.13.el5PAE (ccsafe)      10/21/2008
06:31:43 PM     totsck     tcpsck     udpsck     rawsck    ip-frag     tcp-tw
06:31:48 PM       6951      13868          1          0          0        430
Average:          6951      13868          1          0          0        430
根据TCP状态的变化过程来分析，LAST_ACK属于被动关闭连接过程中的状态
ESTABLISHED->CLOSE_WAIT->（发送ACK）->LAST_ACK->(发送FIN+接收ACK)->CLOSED
现在状态都堆积到LAST_ACK，初步判断问题从上下两个状态着手
调节一下LAST_ACK时间…
[root@ccsafe ~]# sysctl -a |grep last_ack
net.ipv4.netfilter.ip_conntrack_tcp_timeout_last_ack = 30
[root@ccsafe ~]# sysctl -w net.ipv4.netfilter.ip_conntrack_tcp_timeout_last_ack=10
net.ipv4.netfilter.ip_conntrack_tcp_timeout_last_ack = 10
[root@ccsafe ~]# sysctl -p
[root@ccsafe ~]# watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 5.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                     
       6 CLOSE_WAIT
       9 CLOSING
    6420 ESTABLISHED
     693 FIN_WAIT1
     391 FIN_WAIT2
    5081 LAST_ACK
       2 LISTEN
     203 SYN_RECV
      66 TIME_WAIT
检查一下LAST_ACK所对应的应用
[root@ccsafe ~]# netstat -ant|fgrep "LAST_ACK"|cut -b 49-75|cut -d ":" -f1|sort |uniq -c|sort -nr –key=1,7|head -5
     101 220.160.210.6
      46 222.75.65.69
      31 221.0.91.118
      24 222.210.8.160
      22 60.161.81.28
[root@ccsafe ~]#
[root@ccsafe ~]# netstat -an|grep "220.160.210.6"
tcp         0 17280 10.1.1.145:80            220.160.210.6:52787          ESTABLISHED
tcp         1 14401 10.1.1.145:80            220.160.210.6:52513          LAST_ACK     
tcp         1 14401 10.1.1.145:80            220.160.210.6:52769          LAST_ACK     
tcp         1 14401 10.1.1.145:80            220.160.210.6:52768          LAST_ACK     
tcp         0    8184 10.1.1.145:80            220.160.210.6:52515          LAST_ACK     
tcp         1 14401 10.1.1.145:80            220.160.210.6:52514          LAST_ACK     
tcp         0    8184 10.1.1.145:80            220.160.210.6:52781          LAST_ACK     
是TCP80端口的应用，调节一下nginx 的keepalive时间…
[root@ccsafe ~]# /usr/local/nginx/sbin/nginx -t -c /usr/local/nginx/conf/nginx.conf
2008/10/21 19:15:31 [info] 21352#0: the configuration file /usr/local/nginx/conf/nginx.conf syntax is ok
2008/10/21 19:15:31 [info] 21352#0: the configuration file /usr/local/nginx/conf/nginx.conf was tested successfully
[root@ccsafe ~]# ps aux|egrep ‘(PID|nginx)’
USER        PID %CPU %MEM     VSZ    RSS TTY       STAT START    TIME COMMAND
root       8290 0.0 0.0    7572 1124 ?         Ss    Oct04    0:00 nginx: master process /usr/local/nginx/sbin/nginx
nobody     8291 0.2 0.3 19704 13776 ?         S     Oct04 71:35 nginx: worker process      
nobody     8292 0.3 0.2 17604 11680 ?         S     Oct04 77:26 nginx: worker process      
nobody     8293 0.2 0.4 22528 16636 ?         S     Oct04 58:13 nginx: worker process      
nobody     8294 0.3 0.4 24944 19020 ?         S     Oct04 94:07 nginx: worker process      
nobody     8295 0.3 0.5 27496 21508 ?         S     Oct04 84:41 nginx: worker process      
nobody     8296 0.3 0.1 13388 7496 ?         S     Oct04 84:14 nginx: worker process      
nobody     8297 0.2 0.0    9196 3268 ?         S     Oct04 58:21 nginx: worker process      
nobody     8298 0.3 0.2 15392 9504 ?         S     Oct04 75:16 nginx: worker process      
root      21354 0.0 0.0    3896    720 pts/0     S+    19:15    0:00 egrep (PID|nginx)
（动态加载新配置）
[root@ccsafe ~]# kill -HUP 8290
[root@ccsafe ~]#
Every 10.0s: netstat -ant|fgrep cut -b 77-90 |sort |uniq -c                                                
       1 CLOSE_WAIT
    1138 CLOSING
    7161 ESTABLISHED
    1427 FIN_WAIT1
     396 FIN_WAIT2
    5740 LAST_ACK
       2 LISTEN
     350 SYN_RECV
     148 TIME_WAIT
…
[root@ccsafe ~]# netstat -ant|fgrep ":"|cut -b 77-90 |sort |uniq -c
    1151 CLOSING      
    8506 ESTABLISHED
    1452 FIN_WAIT1   
     666 FIN_WAIT2   
    6568 LAST_ACK     
       2 LISTEN      
     429 SYN_RECV     
      92 TIME_WAIT   
…
LAST_ACK不下，而且CLOSING 和FIN_WAIT突增
着重看看可影响主动断开TCP连接时几个参数
tcp_keepalive_intvl:探测消息发送的频率
tcp_keepalive_probes:TCP发送keepalive探测以确定该连接已经断开的次数
tcp_keepalive_time:当keepalive打开的情况下，TCP发送keepalive消息的频率
[root@ccsafe ~]# sysctl -a|grep tcp_keepalive
net.ipv4.tcp_keepalive_intvl = 30
net.ipv4.tcp_keepalive_probes = 2
net.ipv4.tcp_keepalive_time = 160
tcp_retries2:在丢弃激活(已建立通讯状况)的TCP连接之前﹐需要进行多少次重试
[root@ccsafe ~]# sysctl -a |grep tcp_retries
net.ipv4.tcp_retries2 = 15
net.ipv4.tcp_retries1 = 3
加速处理那些等待ACK的LAST_ACK，减少等待ACK的LAST_ACK的重试次数
[root@ccsafe ~]# sysctl -w net.ipv4.tcp_retries2=5
net.ipv4.tcp_retries2 = 5
减少keepalive发送的频率
[root@ccsafe ~]# sysctl -w net.ipv4.tcp_keepalive_intvl=15
net.ipv4.tcp_keepalive_intvl = 15
[root@ccsafe ~]# sysctl -p
排除syncookies的影响
[root@ccsafe ~]# !ec
echo "0" >/proc/sys/net/ipv4/tcp_syncookies
[root@ccsafe ~]# echo "1" >/proc/sys/net/ipv4/tcp_syncookies
[root@ccsafe ~]# sysctl -a|grep tcp_keepalive               
net.ipv4.tcp_keepalive_intvl = 30
net.ipv4.tcp_keepalive_probes = 2
net.ipv4.tcp_keepalive_time = 160
[root@ccsafe ~]# sysctl -a|grep syncookies
net.ipv4.tcp_syncookies = 1
延长keepalive检测周期，保留ESTABLISHED数量
[root@ccsafe ~]# echo "1800" >/proc/sys/net/ipv4/tcp_keepalive_time
[root@ccsafe ~]# echo "5" >/proc/sys/net/ipv4/tcp_keepalive_probes
[root@ccsafe ~]# echo "15" >/proc/sys/net/ipv4/tcp_keepalive_intvl
[root@ccsafe ~]# sysctl -a|grep tcp_keepalive                       
net.ipv4.tcp_keepalive_intvl = 15
net.ipv4.tcp_keepalive_probes = 5
net.ipv4.tcp_keepalive_time = 1800
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       1 CLOSE_WAIT
     363 CLOSING
    5145 ESTABLISHED
    1073 FIN_WAIT1
     174 FIN_WAIT2
    6042 LAST_ACK
       2 LISTEN
     301 SYN_RECV
      85 TIME_WAIT
LAST_ACK不下，但是CLOSING有所回落
tcp_orphan_retries:在近端丢弃TCP连接之前﹐要进行多少次重试。
[root@ccsafe ~]# sysctl -a|grep tcp_orphan
net.ipv4.tcp_orphan_retries = 0
关键，丢TCP太频繁了，以至于后勤都跟不上。设置 丢弃之前的重试次数
[root@ccsafe ~]# echo "3" >/proc/sys/net/ipv4/tcp_orphan_retries
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       1 CLOSE_WAIT
      24 CLOSING
    5422 ESTABLISHED
     279 FIN_WAIT1
     214 FIN_WAIT2
    1966 LAST_ACK
       2 LISTEN
     269 SYN_RECV
      74 TIME_WAIT
上下调节该值，找个合适的临界点
[root@ccsafe ~]# echo "7" >/proc/sys/net/ipv4/tcp_orphan_retries                  
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       1 CLOSE_WAIT
     175 CLOSING
    5373 ESTABLISHED
     436 FIN_WAIT1
     209 FIN_WAIT2
    3184 LAST_ACK
       2 LISTEN
     283 SYN_RECV
     110 TIME_WAIT
恢复，同时FIN_WAIT1的值过高。考虑减少tcp_fin_timeout时间
[root@ccsafe ~]# echo "2" >/proc/sys/net/ipv4/tcp_orphan_retries                  
[root@ccsafe ~]# sysctl -a|grep tcp_fin
net.ipv4.tcp_fin_timeout = 10
[root@ccsafe ~]# echo "5" >/proc/sys/net/ipv4/tcp_fin_timeout
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       2 CLOSE_WAIT
      17 CLOSING
    5665 ESTABLISHED
     145 FIN_WAIT1
     141 FIN_WAIT2
    1068 LAST_ACK
       2 LISTEN
     287 SYN_RECV
      68 TIME_WAIT
相比FIN_WAIT，SYN_RECV的值偏高。加大发送synack的质量
[root@ccsafe ~]# sysctl -a|grep synack
net.ipv4.tcp_synack_retries = 1
[root@ccsafe ~]# echo "2" >/proc/sys/net/ipv4/tcp_synack_retries
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       3 CLOSE_WAIT
      16 CLOSING
    5317 ESTABLISHED
     200 FIN_WAIT1
     158 FIN_WAIT2
    1001 LAST_ACK
       2 LISTEN
     303 SYN_RECV
      78 TIME_WAIT
[root@ccsafe ~]# sysctl -a|grep keepalive
net.ipv4.tcp_keepalive_intvl = 15
net.ipv4.tcp_keepalive_probes = 5
net.ipv4.tcp_keepalive_time = 1800
[root@ccsafe ~]# watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                          
       1 CLOSE_WAIT
       7 CLOSING
    5356 ESTABLISHED
     175 FIN_WAIT1
     136 FIN_WAIT2
    1045 LAST_ACK
       2 LISTEN
     345 SYN_RECV
      64 TIME_WAIT
减少keepalive的检测周期，LAST_ACK上升
[root@ccsafe ~]# echo "10" >/proc/sys/net/ipv4/tcp_keepalive_intvl
[root@ccsafe ~]# echo "1" >/proc/sys/net/ipv4/tcp_synack_retries                  
[root@ccsafe ~]# !wat
watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                                                
       1 CLOSE_WAIT
      13 CLOSING
    5605 ESTABLISHED
     212 FIN_WAIT1
     131 FIN_WAIT2
    1143 LAST_ACK
       2 LISTEN
     252 SYN_RECV
      79 TIME_WAIT
恢复
[root@ccsafe ~]# echo "15" >/proc/sys/net/ipv4/tcp_keepalive_intvl               
[root@ccsafe ~]# watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                        
       3 CLOSE_WAIT
      14 CLOSING
    5862 ESTABLISHED
     230 FIN_WAIT1
     205 FIN_WAIT2
    1064 LAST_ACK
       2 LISTEN
     244 SYN_RECV
      59 TIME_WAIT
[root@ccsafe ~]# watch -n 10 "netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c"
Every 10.0s: netstat -ant|fgrep cut -b 77-90|sort |uniq -c                        
       3 CLOSE_WAIT
      26 CLOSING
    6712 ESTABLISHED
     270 FIN_WAIT1
     230 FIN_WAIT2
     994 LAST_ACK
       2 LISTEN
     254 SYN_RECV
      73 TIME_WAIT
[root@ccsafe ~]#
目前LAST_ACK占ESTABLISHED的量在15%左右

[source]

MySQL进入Oracle产品体系，获得了更多研发投入，新一代MySQL产品—MySQL5.5即将面世，较之之前的5.1版本，将获得诸多特性方面的提升，简单总结如下：

1. 默认存储引擎更改为InnoDB

InnoDB作为成熟、高效的事务引擎，目前已经广泛使用，但MySQL5.1之前的版本默认引擎均为MyISAM，此次MySQL5.5终于做到与时俱进，将默认数据库存储引擎改为InnoDB，并且引进了Innodb plugin 1.0.7。此次更新对数据库的好处是显而易见的：InnoDB的数据恢复时间从过去的一个甚至几个小时，缩短到几分钟(InnoDB plugin 1.0.7，InnoDB plugin 1.1， 恢复时采用红-黑树)。InnoDB Plugin 支持数据压缩存储，节约存储，提高内存命中率，并且支持adaptive flush checkpoint, 可以在某些场合避免数据库出现突发性能瓶颈。

Multi Rollback Segments： 原来InnoDB只有一个Segment，同时只支持1023的并发。现已扩充到128个Segments，从而解决了高并发的限制。

2. 多核性能提升

Metadata Locking (MDL) Framework替换LOCK_open mutex (lock)，使得MySQL5.1及过去版本在多核心处理器上的性能瓶颈得到解决，官方表示将继续增强对MySQL多处理器支持，直至MySQL性能“不受处理器数量的限制”

3. 复制功能(Replication)加强

MySQL复制特性是互联网公司应用非常广泛的特性，作为MySQL最实用最简单的扩展方式，过去的异步复制方式已经有些不上形势，对某些用户来说“异步复制”意味着极端情况下的数据风险，MySQL5.5将首次支持半同步(semi-sync replication)在MySQL的高可用方案中将产生更多更加可靠的方案。另外Slave fsync tunning;Relay log corruption recovery和Replication Heartbeat也将实现。

4. 增强表分区功能

MySQL 5.5的分区对用户绝对是个好消息，更易于使用的增强功能，以及TRUNCATE PARTITION命令都可以为DBA节省大量的时间，有时对最终用户亦如此：

1) 非整数列分区：任何使用过MySQL分区的人应该都遇到过不少问题，特别是面对非整数列分区时，MySQL 5.1只能处理整数列分区，如果你想在日期或字符串列上进行分区，你不得不使用函数对其进行转换。很麻烦，而MySQL 5.5中新增了两类分区方法，RANG和LIST分区法，同时在新的函数中增加了一个COLUMNS关键词。在MySQL 5.1中使用分区另一个让人头痛的问题是date类型(即日期列)，你不能直接使用它们，必须使用YEAR或TO_DAYS转换这些列，但在MySQL 5.5中情况发生了很大的变化，现在在日期列上可以直接分区，并且方法也很简单;

2) 多列分区：COLUMNS关键字现在允许字符串和日期列作为分区定义列，同时还允许使用多个列定义一个分区;

3) 可用性增强：truncate分区。分区最吸引人的一个功能是瞬间移除大量记录的能力，DBA都喜欢将历史记录存储到按日期分区的分区表中，这样可以定期删除过时的历史数据。 但当你需要移除分区中的部分数据时，事情就不是那么简单了，删除分区没有问题，但如果是清空分区，就很头痛了，要移除分区中的所有数据，但需要保留 分区本身，你可以：使用DELETE语句，但我们知道DELETE语句的性能都很差。使用DROP PARTITION语句，紧跟着一个EORGANIZE PARTITIONS语句重新创建分区，但这样做比前一个方法的成本要高出许多。MySQL 5.5引入了TRUNCATE PARTITION，它和DROP PARTITION语句有些类似，但它保留了分区本身，也就是说分区还可以重复利用。TRUNCATE PARTITION应该是DBA工具箱中的必备工具;

4) 更多微调功能：TO_SECONDS：分区增强包有一个新的函数处理DATE和DATETIME列，使用TO_SECONDS函数，你可以将日期/时间列转换成自0年以来的秒数，如果你想使用小于1天的间隔进行分区，那么这个函数就可以帮到你。

5. Insert Buffering 如果在buffer pool中没找到数据，那么直接buffer起来，避免额外的IO;Delete & Purge Buffering 跟插入一样，如果buffer pool中没有命中，先buffer起来，避免额外的IO。

6. Support for Native AIO on Linux

以上的特性在MySQL 5.5的社区版当中都将包括，在MySQL企业版当中，除以上更新之外，Oracle还加强了更多实用的企业级功能，包括：

1. 实现在线物理热备

MySQL 企业版将包含Innodb Hotbackup(这也许是MySQL和InnDB多年之后重新聚首的新亮点)，从而一举解决过去MySQL无法进行可靠的在线实时物理备份的问题， InnoDB Hot Backup 不需要你关闭你的服务器也不需要加任何锁或影响其它普通的数据操作，这对MySQL DBA来说应该是一个不错的消息。

2. MySQL Enterprise Monitor 2.2 & Oracle Enterprise Monitor

是的，你没有看错，MySQL将可以被Oracle Enterprise Monitor监控，这是一个实现起来并不复杂，但在过去绝无可能的变化。并且MySQL企业版监控器(MySQL Enterprise Monitor)得到了更大的加强，版本更新至2.2，对MySQL服务器资源占用降低到可以忽略的地步，集成了监控，报警，SQL语句分析和给出优化建议，MySQL的一些开源监控方案相比之下显得过于简陋，对企业客户来说，MySQL变得更加可靠。

3. MySQL Workbench

过去MySQL的图形界面工具做的实在是令人难以恭维，当然这也给众多MySQL管理工具提供了市场空间，现在Oracle打算将MySQL做得比SQL-Server更加简单易用，MySQL Workbench是一款专为MySQL设计的ER/数据库建模工具，可以用来设计和创建新的数据库图示，建立数据库文档，以及进行复杂的MySQL 迁移等操作，因此内置workbench将使MySQL使用起来更简便高效。

4. 关于未来的重要提醒：Oracle的管理工具，MySQL也将能够使用，Oracle比MySQL社区想象要聪明，不是吗?当然MySQL 5.5我们还没看到这个变化，但变化已经在时间表上，MySQL社区版也能够被Oracle管理工具管理，前提你得是Oracle数据库的用户。

如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。
    我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I’m matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
    解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
    之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。
    个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。
    假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B = a b a b a c b
    j = 1 2 3 4 5 6 7
    此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j’。j’可能是多少呢？仔细想一下，我们发现，j’必须要使得B[1..j]中的头j’个字母和末j’个字母完全相等（这样j变成了j’后才能继续保持i和j的性质）。这个j’当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =     a b a b a c b
    j =     1 2 3 4 5 6 7
    从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
    再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =     a b a b a c b
    j =     1 2 3 4 5 6 7
    由于P[5]=3，因此新的j=3：
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =         a b a b a c b
    j =         1 2 3 4 5 6 7
    这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =             a b a b a c b
    j =             1 2 3 4 5 6 7
    现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：
    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =               a b a b a c b
    j =             0 1 2 3 4 5 6 7
    终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。
    这个过程的代码很短（真的很短），我们在这里给出：

j:=0;
for i:=1 to n do
begin
   while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
   if B[j+1]=A[i] then j:=j+1;
   if j=m then
   begin
      writeln('Pattern occurs with shift ',i-m);
      j:=P[j];
   end;
end;

最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。

    这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。

    现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。

    为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。

    预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],…,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：

        1 2 3 4 5 6 7

    B = a b a b a c b

    P = 0 0 1 2 3 ?

    P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。

    怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似：

P[1]:=0;
j:=0;
for i:=2 to m do
begin
   while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
   if B[j+1]=B[i] then j:=j+1;
   P[i]:=j;
end;

最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。

    串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。

转自：Matrix67