一，安装jdk：

（这里的方法是用于ubuntu或debian的，把下载的jdk构建成deb包，我觉得是为了便于包管理，否则删除的时候都不知道删除哪些文件，很麻烦。）
1. 获取JDK
可以选择从Java官方下载: ::URL::http://java.sun.com 或者从其它网站下载.我用的版本是:jdk-1_5_0-linux-i586.bin

2. 构建打包环境
Debian专门提供了SDK 的DEB包构建工具: java-package,而Ubuntu是基于Debian的,所以
# apt-get install -u java-package fakeroot

在apt-get之前最好update一下

3. 创建.deb 软件包

这一步要以普通用户运行,如果以Root运行是不允许的.会有下面的提示:

You are real root -- unfortunately, some Java distributions have
install scripts that directly manipulate /etc, and may cause some
inconsistencies on your system. Instead, you should become a
non-root user and run:

fakeroot make-jpkg jdk-1_5_0-linux-i586.bin

which will allow no damage to be done to your system files and
still permit the Java distribution to successfully extract.

Aborting.

以普通用户执行:
＄ fakeroot make-jpkg jdk-1_5_0_06-linux-i586.bin
接下来做一些必要的选择.几分钟后,就应当出现软件包创建成功的提示.你在当前目录下会发现类似:
sun-j2sdk1.5_1.5.0+update00_i386.deb的软件包

4. 安装
切换回root执行以下命令:
# dpkg -i sun-j2sdk1.5_1.5.0+update06_i386.deb

5.配置环境

在 ~/.bashrc脚本文件中加入类似如下内容

PATH=＄PATH:/usr/lib/j2sdk1.5-sun/bin:/usr/lib/j2sdk1.5-sun/jre/bin
JAVA_HOME=/usr/lib/j2sdk1.5-sun
JRE_HOME=/usr/lib/j2sdk1.5-sun/jre
CLASSPATH=.:/usr/lib/j2sdk1.5-sun/lib/tools.jar:/usr/lib/j2sdk1.5-sun/lib/dt.jar
export PATH
export JRE_HOME
export JAVA_HOME
export CLASSPATH

6. 测试
创建一个简单的java程序(Hello.java)
public class Hello
{
public Hello()
{
}

public static void main(String[] args)
{
System.out.println("Hello World!";
}

}
然后
＄javac Hello.java
检查当前目录会生成一个Hello.class的文件, 然后运行
＄java Hello
Hello World!
OK,测试成功!

7. 中文化安装中文字体:
在 ＄JAVA_HOME/jre/lib/fonts/ 目录下创建一个fallback目录.
复制中文字体(例如:simsun.ttf 至此目录.

8. 安装插件
对于此种方法安装的Java环境, 浏览器插件文件位置应当位于:
/usr/lib/j2sdk1.5-sun/jre/plugin/i386/ns7/libjavaplugin_oji.so

以 firefox1.5.0.1为例:
# cd /usr/lib/mozilla-firefox/plugins
# ln -s \
/usr/lib/j2sdk1.5-sun/jre/plugin/i386/ns7/libjavaplugin_oji.so

卸载JDK:
# apt-get remove --purge sun-j2sdk1.5
卸载插件, 直接删除符号链接:
# rm /usr/lib/mozilla-firefox/plugins/libjavaplugin_oji.so

二，安装jython：

1，http://www.jython.org/Project/installation.html下载jython安装文件，运行命令“java -jar jython_installer-2.2rc2.jar”，jython即安装成功。比如安装在/home/justin/java/jython2.2目录下

2，把jython包加入classpath，即把上面的classpath改为：CLASSPATH=.:/usr/lib/j2sdk1.5-sun/lib/tools.jar:/usr/lib/j2sdk1.5-sun/lib/dt.jar:/home/justin/java/jython2.2/jython.jar
此后就可以在java文件中加入python库了，例如：

3，将选择的/home/justin/java/jython2.2/jython安装路径添加到 PATH 环境变量。现在只要输入“jython”就可以运行交互式 PATH ：
$ jython
Jython 2.1 on java1.4.0_01 (JIT: null)
Type "copyright", "credits" or "license" for more information.
>>># 通过 Jython 访问标准 Java 库
>>> from java.util import Random
>>> rng = Random()
>>> i = rng.nextBoolean()
>>> print i

jython 解释器对于快速检查和作提示都很方便，但您不必在这其中完成所有工作 ― Jython 还允许您在源文件中编写代码，并随后运行该代码（
from java.util import Random
rng = Random()
#This is a comment in Jython
print "Flipping a coin..."
if rng.nextBoolean():
    print "Came up heads"
else:
    print "Came up tails"
用jython运行该文件，即可
一，网络时间服务：

1. 与一个已知的时间服务器同步
公司配置：
#synchronize time with fw.exoweb.net
00 0 1 * * root rdate -s fw.exoweb.net

2. 配置网络时间协议（ntp）

1. 让linux自动同步时间

vi /etc/crontab
加上一句：
00 0 1 * * root rdate -s time.nist.gov

time.nist.gov 是一个时间服务器.

2. 时间服务器配置(192.168.10.1)

1）. # rpm -ivh ntp-4.1.2-4.EL3.1.i386.rpm
2）. # vi /etc/ntp.conf
注释一行
restrict default ignore
加入一行
restrict 192.168.10.0 mask 255.255.255.0 notrust nomodify notrap
3）. # vi /etc/ntp/step-tickers
加入一行
pool.ntp.org
这样每次ntpd启动时，会自动连接该国际标准时间服务器；
4）. # service ntpd start
5）. # netstat -an |grep 123
确保该端口以udp方式开放

时间客户端配置(192.168.10.2)
1）. # ntpdate 192.168.10.2
应该显示同步成功
2）. # crond -e
加入
0-59/10 * * * * /usr/sbin/ntpdate 192.168.10.1
表示每隔10分钟同步一次时间

二, 出现  must be setuid root 错误
解决办法：

ls -l  /usr/bin/sudo
chown root:root /usr/bin/sudo
chmod 4755 /usr/bin/sudo
reboot

三，用nohup命令让Linux下程序永远在后台执行

Unix/Linux下一般想让某个程序在后台运行，很多都是使用 & 在程序结尾来让程序自动运行。比如我们要运行mysql在后台：

         /usr/local/mysql/bin/mysqld_safe --user=mysql &

但是我们很多程序并不象mysqld一样可以做成守护进程，可能我们的程序只是普通程序而已，一般这种程序即使使用 & 结尾，如果终端关闭，那么程序也会被关闭。为了能够后台运行，我们需要使用nohup这个命令，比如我们有个start.sh需要在后台运行，并且希望在 后台能够一直运行，那么就使用nohup：

            nohup /root/start.sh &

四， python反编译工具
decompyle

五，rpm包转deb包工具： fakeroot and alien
fakeroot alien -d *.rpm

六， 保存ftest信息并查看
nohup ./nordicbetsite ftest -v2 >ftest_result 2>&1 &
tail -f ftest_result

七， ip信息
ifconfig

八， dpkg命令
查看python2.5是否安装： dpkg -l python2.5
查看名称含有python的所有软件： dpkg -l | grep python
查看python2.5软件包的位置： dpkg -L python2.5

九， 分区情况
查看所有分区情况： df -h
查看某个软件在哪个分区： df -h ***


命令行下载工具 ，转自：http://blog.chinaunix.net/u/9465/showart.php?id=186155，方便在虚拟机上开发，不用再从外面拷贝到虚拟机上了。

   对于喜欢命令行操作及追求高效率、高速度下载的朋友，推荐使用命令行下载工具。命令行工具不但使用方便，而且大多具有很高的下载速度及下载效率，尤其适合 于大批量下载文件。下面就为大家详细介绍一下这些工具。

    Wget     Wget是一个十分常用命令行下载工具，多数Linux发行版本都默认包含这个工具。如果没有安装可在http://www.gnu.org/software/wget/wget.html下 载最新版本，并使用如下命令编译安装：
    #tar zxvf wget-1.9.1.tar.gz
    #cd wget-1.9.1 #./configure
    #make #make install
它的用法很简单，Wget使用格式如下： #wget [选项] [下载地址] 1.Wget常用参数 ◆-b：后台下载，Wget默认的是把文件下载到当前目录。 ◆-O：将文件下载到指定的目录中。 ◆-P：保存文件之前先创建指定名称的目录。 ◆-t：尝试连接次数，当Wget无法与服务器建立连接时，尝试连接多少次。 ◆-c：断点续传，如果下载中断，那么连接恢复时会从上次断点开始下载。     除了上述常用功能，Wget还支持HTTP和FTP代理功能，编辑其配置文件“/etc/wgetrc”即可。具体方法是使用VI编辑器打开上述文件，将 “http_proxy”和“ftp_proxoy”前的#去掉，然后在这两项后输入相应的代理服务器的地址，保存退出即可。此外，Wget还可下载整个 网站，如下载http://man.chinaunix.net整个Man手册中心。只需输入如下命令即可： #wget -r -p -np -k http://man.chinaunix.net 其中-r参数是指使用递归下载，-p是指下载所有显示完整网页所以需要的文件，如图片等，-np是指不搜索上层目录，-k则是指将绝对链接转换为相对链 接。

     Prozilla     Prozilla也是一个十分流行的命令行下载工具，支持多线程下载和断点续传功能。可到http://prozilla.genesys.ro/下 载最新的1.3.7.4安装包，下载安装包后使用如下命令进行安装：
    #tar zxvf prozilla-1.3.7.4.tar.gz
    #cd prozilla-1.3.7.4
    #./configure #make
    #make install
Prozilla命令格式如下： #proz [参数] [下载地址] 常用的选项有： ◆-k=n ：设置n个线程下载。不加此参数指定线程数，Prozilla默认为4线程下载。 ◆-P, --directory-prefix=DIR：指定将下载的文件保存在DIR/目录。 ◆-r, --resume：继续下载未完成的文件。如果要指定线程数下载可用如下命令： #proz -k=5 http://64.12.204.21/pub/mozilla.org/firefox/releases/1.0/linux-i686/zh-CN/firefox-1.0.installer.tar.gz 这样便以5线程进行文件的下载，并将文件保存到当前目录。和Wget一样，Prozilla也提供了续传功能，下载中断后，重新输入上述命令，就会出现提 示续传，按R键就可继续下载了。

     MyGet     MyGet目标设计成一个可扩展的，拥有丰富界面的多线程下载工具，它支持HTTP、FTP、HTTPS、MMS、RTSP等协议。在http://myget.sourceforge.net/release/myget-0.1.0.tar.bz2下 载其最新版本0.1.0，下载后使用如下命令安装：
     #tar jxvf myget-0.1.0.tar.bz2
    #cd myget-0.1.0 #./configure
    #make
    #make install
MyGet命令格式如下： #mytget [选项] [下载地址] 常用的选项： ◆-d [目录]：指定下载到的文件在本地存放的位置，默认当前目录。 ◆-f [文件]：指定下载文件名称。 ◆-h：帮助选项。 ◆-n [线程数]：下载线程数量，默认为4个。 ◆-x [代理服务器地址]：设置代理服务器地址，如“-x http://user:password@host:port”。 MyGet常用的形式如下： #mytget －d /root/ -n 10 http://lumaqq.linuxsir.org/download/patch/lumaqq_2004t_patch_2005.07.21.00.00.zip        

    Linuxdown     Linuxdown是一个命令行多线程下载工具，最多可支持30线程的下载。在https://gro.clinux.org/frs/download.php/1015/linuxdown-1.0.0.tar.gz下 载最新的1.1.0版本。然后使用如下命令进行编译安装：
    #tar zxvf linuxdown-1.1.0.tar.gz
    #cd dandelion/
    #make
    #make install
linuxdown格式为： #linuxdown [下载地址] [选项] [线程数]     需要注意的是下载地址和选项都需要西文引号括起来，线程数不可超过30个。一个典型的下载如下： #linuxdown "http://lumaqq.linuxsir.org/download/patch/lumaqq_2004t_patch_2005.07.21.00.00.zip" 30

    Curl     Curl也是Linux下不错的命令行下载工具，小巧、高速，唯一的缺点是不支持多线程下载。在http://curl.haxx.se/download/curl-7.14.0.tar.gz下 载最新版本。下载后便可使用如下命令编译安装：         #tar zxvf curl-7.14.0.tar.gz
    #cd curl-7.14.0/
    #./configure
    #make
    #make test
    #make install
Curl使用格式如下： #curl [选项][下载地址] Curl典型下载如下： #curl -O http://10.1.27.10/~kennycx/tools/lumaqq_2004-linux_gtk2_x86_with_jre.tar.gz     使用Curl下载一个文件并保存到当前目录。此外，Curl虽然不支持多线程下载，但它可同时下载多个文件或下载文件的某一部分，可使用如下命令实现： #curl -r 0-199 http://www.netscape.com/ 获得文件的前200 bytes。     对于常用的代理下载Curl也可轻松实现，具体操作如下： #curl -x 10.1.27.10:1022 ftp://ftp.funet.fi/README 使用代理地址为10.1.27.10端口为1022的代理服务器下载一个文件。 #curl -U user:passwd -x 10.1.27.10:1022 ftp://ftp.funet.fi/README 如果代理服务器需要特别的验证，则需要在user:passwd处输入合法的帐号和密码。

    Axel     Axel是命令行下的多线程下载工具，支持断点续传，速度通常情况下是Wget的几倍。可在http://www.linuxfans.org/nuke/modules.php?name=Site_Downloads&op=mydown&did=1697下 载。下载后使用如下命令编译安装：
    #tar zxvf axel-1.0a.tar.gz
    #cd axel-1.0a/
    #./configure
    #make
    #make install
基本的用法如下： #axel [选项] [下载目录] [下载地址] 一个典型下载如下： #alex -n 10 -o /home/kennycx/ http://10.1.27.10/~kennycx/tools/lumaqq_2004-linux_gtk2_x86_with_jre.tar.gz 用10线程将指定路径的文件下载到/home/kennycx/这个目录下。     本文详细介绍了Linux中常用的下载工具，这些下载工具功能上各有千秋，使用上都比较简单，所以无论是初学者还是Linux高手总有一款适合你。

Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。 也许最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable，但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，它创建一个线程安全的Map对象，并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时，你不能切断Hashtable中的同步（比如在一个单线程的应用程序中），而且同步增加了很多处理费用。 第三点不同是，只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。如果有必要，用containKey()方法来区别这两种情况。 一些资料建议，当需要同步时，用Hashtable，反之用HashMap。但是，因为在需要时，HashMap可以被同步，HashMap的功能比Hashtable的功能更多，而且它不是基于一个陈旧的类的，所以有人认为，在各种情况下，HashMap都优先于Hashtable。 关于Properties 有时侯，你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子，如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法，但Java提供了另外一种方法。 Java.util.Properties类是Hashtable的一个子类，设计用于String keys和values。Properties对象的用法同Hashtable的用法相象，但是类增加了两个节省时间的方法，你应该知道。 Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反，用来读取文件，并设定Properties对象来包含keys和values。 注意，因为Properties扩展了Hashtable，你可以用超类的put()方法来添加不是String对象的keys和values。这是不可取的。另外，如果你将store()用于一个不包含String对象的Properties对象，store()将失败。作为put()和get()的替代，你应该用setProperty()和getProperty()，它们用String参数。 好了，我希望你现在可以知道如何用hashtables来加速你的处理了。     下面再转一篇关于两个类的区别，比较简单的过一下 最近同学找工作，经常被问到这个问题rt，所以。。。。。。   HashTable的应用非常广泛，HashMap是新框架中用来代替HashTable的类，也就是说建议使用HashMap，不要使用HashTable。   这里简单分析他们的区别。  1.HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。（最主要的区别） 2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以，只容许有一个null值的key，可以有多个null值的value)。 3.HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。 4.HashTable使用Enumeration，HashMap使用Iterator。 以上只是表面的不同，它们的实现也有很大的不同。 5.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。 6.哈希值的使用不同，HashTable直接使用对象的hashCode，代码是这样的： int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; 而HashMap重新计算hash值，而且用与代替求模： int hash = hash(k); int i = indexFor(hash, table.length); static int hash(Object x) { 　　 int h = x.hashCode(); 　　 h += ~(h << 9); 　　 h ^= (h >>> 14); 　　 h += (h << 4); 　　 h ^= (h >>> 10); 　　 return h; } static int indexFor(int h, int length) { 　　 return h & (length-1); } 以上只是一些比较突出的区别，当然他们的实现上还是有很多不同的，比如 HashMap对null的操作。

java.math.Math类常用的常量和方法：

Math.PI 记录的圆周率
Math.E记录e的常量
Math.abs 求绝对值
Math.sin 正弦函数 Math.asin 反正弦函数
Math.cos 余弦函数 Math.acos 反余弦函数
Math.tan 正切函数 Math.atan 反正切函数 Math.atan2 商的反正切函数
Math.toDegrees 弧度转化为角度 Math.toRadians 角度转化为弧度
Math.ceil 得到不小于某数的最大整数
Math.floor 得到不大于某数的最大整数
Math.IEEEremainder 求余
Math.max 求两数中最大
Math.min 求两数中最小
Math.sqrt 求开方
Math.pow 求某数的任意次方, 抛出ArithmeticException处理溢出异常
Math.exp 求e的任意次方
Math.log10 以10为底的对数
Math.log 自然对数
Math.rint 求距离某数最近的整数（可能比某数大，也可能比它小）
Math.round 同上，返回int型或者long型（上一个函数返回double型）
Math.random 返回0，1之间的一个随机数

java.math.BigInteger(大整数)：
BigInteger bi1=new BigInteger("1234567890123456890");
BigInteger bi2=BigInteger.valueOf(123L);
bi1=bi1.add(bi2);//b1+b2
bi1=bi1.multiply(bi2);//b1*b2
bi1=bi1.subtract(bi2);//b1-b2
bi1=bi1.divide(bi2);// b1/b2

java.math.BigDecimal(大浮点数):
BigDecimal bd = new BigDecimal("3.1415926");
bd = bd.setScale(2,BigDecimal.ROUND_DOWN);//取3.1415926小数点后面二位

1、classpath不用再定义.;***\lib\tools.jar;***\lib\rt.jar，因为jre会自动寻找lib目录

2、如果想要用jdk5.0编译出jdk1.4可运行的class文件需要带-source和-target两个参数
eg: javac -source 1.4 -target 1.4 Hello.java

3、命令行读入int i = System.in.read();//读入输入字符串的第一个字符的int值；
读整个字符串时：
public class Test{
 public static void main(String[] args){
  byte[] a = new byte[100];
  try {
   System.in.read(a);
  } catch (IOException e) {
   e.printStackTrace();
  }
  System.out.println(new String(a));
 }
}

jdk5.0中命令行读入的方法更好，可以读成不同类型的数据：
//Scanner取得输入的依据是：空格键、Tab键或Enter键
import java.util.Scanner;

public class ScannerDemo{
 public static void main(String[] args){
  Scanner scanner = new Scanner(System.in);
  System.out.print("请输入姓名");
  System.out.printf("您好%s!\n", scanner.next());
  System.out.print("请输入年龄");
  System.out.printf("您好%d!\n", scanner.nextInt());
  //还有scanner.nextFloat(),scanner.nextBoolean();
 }
}

//BufferReader取得输入的依据是：Enter键
import java.io.*;

public class BufferReaderDemo{
 public static void main(String[] args){
  BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("请输入一系列文字");
  String text = bufferedReader.readLine();
  System.out.print("您输入的是：" + text);
 }
 }
}

4、aotuboxing和unboxing，jdk5.0可以自动对基本类型和它们的包装类型自动转换。

5、数组
数组的索引值:由0开始的原因：索引值表示偏移量，第一个值的偏移为0.

数组的初始化：byte/short/int = 0; long = ol; float = o.0f; double = 0.0d; char = \u0000; boolean = false; Objective = null;

一维数组：
法一：int[] i = {1,2,3};
法二：int[] i = new int[]{1,2,3};
法三：int[] i = new int[3]; i[0] = 1; i[1] = 2; i[2] = 3;

多维数组：
法一：int[][] i = {{...},...,{...}};
法二：int[][] i = int[][]{{...},...,{...}};
法三：int[][] i = int[3][]; i[0] = {1,2,3}; i[0] = {1,2,3}; i[0] = {1,2,3};
法四：int[][] i = int[3][3];

不规则数组：行列不等

数组的常用方法：都是java.util.Arrays类的方法
sort()//制定数组快速排序
binarySearch()//对已排序的数组搜索，找到返回索引，否则返回负值
fill()//根据数组的数据类型填默认值
equals()//比较两数组
jdk1.5中新增:
deepEquals()//深度比较
deepToString()//深度输出

foreach与数组：
String[] a = {"asd","efge","efg"};
for(String s : a)
 System.out.println(s);

5、字符串
java.lang.StringBuilder是jdk5.0新增的类，它与StringBuffer具有相同接口，只是单机非多线程情况下用StringBuilder效率较高，因为StringBuilder没处理同步问题；多线程下用StringBuffer好。

字符串分离：
 String s = "23/twomen/tlai/t jeje";
 String[] a = s.split("/t");
 for(int i = 0; i < a.length; i++){
  System.out.print(a[i] +　" ");
 }
输出结构：23 women lai  jeje

由于工作关系学习jdk5.0的步伐暂时停止，以后有机会继续看《jdk5.0学习笔记》，回来写我的总结。

1 术语定义

在字符串匹配问题中，我们期待察看串T中是否含有串P。
其中串T被称为目标串，串S被称为模式串。

2 朴素匹配算法

进行字符串匹配，最简单的一个想法是：

可以看见，这个算法（假定m>>n）的复杂度是O(mn)，其中m是T的长度，n是P的长度。这种算法的缺陷是匹配过程中带有回溯——准确地说是T串存在回溯，也就是当匹配不成功的时候，之前进行的匹配完全变为无用功，所有的比较需要重新开始。

3 KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt提出的无回溯的字符串匹配算法，算法的核心思想就是设法在匹配失败的时候，尽量利用之前的匹配结果，消除T串的回溯问题。那么如何消除回溯呢？请看下面的例子：

假设P=abacd，如果T=abax...，当从头开始匹配到字符c时，若c=x，显然，匹配过程继续；当c≠x时，按照朴素的匹配算法，T串会发生回溯，之后T串会从第2个字符b开始重新匹配，而不是从匹配失败的字符x开始继续。但是显然，对于上述的匹配过程，T串不需要从b开始重新匹配，它只需要从x开始和P的b字符继续匹配即可。如下：
匹配过程：
P=abacd
T=abax....
     ^----比较到此处时发生匹配失败
朴素匹配算法：
P= abacd
T=abax...
   ^----回溯到b，重新开始和P的匹配
KMP算法：
P=  abacd
T=abax...
     ^----T串不回溯，从x处继续匹配

现在的问题是，按照KMP算法，匹配失败的时候，P串需要重新调整位置，但是调整的依据是什么？Knuth等人发现，P调整位置的依据和P的构造有关，和T无关。具体来说，定义失效函数：f(j)=k，其中0<=k<=j，且k是使得p₀p₁...p_k-1 = p_j-k+1p_j-k+2...p_j成立的最大整数。建立失效函数的算法如下：
public void Build() {
 if(pattern == null)
  throw new Exception("KMP Exception : null pattern");
 array = new int[pattern.Length];
 int i = 0, s = pattern.Length;
 if(s > 1)
  array[0] = 0;
 for(i = 1; i < s; i++) {
  if(pattern[i] == pattern[array[i - 1]])
   array[i] = array[i - 1] + 1;
  else
   array[i] = 0;
 }
}

匹配过程如下：
public int Match(String target, int start) {
 if(array == null || pattern == null || target == null)
  return -1;
 int target_index = start;
 int pattern_index = 0;
 int token_length = target.Length;
 int pattern_length = pattern.Length;
 while(target_index < token_length && pattern_index < pattern_length) {
  if(target[target_index] == pattern[pattern_index]) {
   target_index++;
   pattern_index++;
  } else {
   if(pattern_index == begin)
    target_index++;
   else
    pattern_index = array[pattern_index - 1];
  }
 }
 if(pattern_index == pattern_length)
  return target_index - pattern_length;
 return -1;
}

4 支持通配符?和*的KMP算法

KMP算法虽然能够进行字符串匹配，但是，在实践中字符串匹配往往还要支持通配符，MS系统中最常见的通配符是?和*。其中，?可以代表一个字符（不能没有），*可以代表任意多个字符（可以为空）。经典的KMP算法针对通配符是无能为力的，但是经过简单的改造，KMP算法也可以识别通配符。

首先是?，根据?的功能，?表示任意字符，也就是说在匹配过程中，?永远匹配成功。因此对匹配函数的修改十分简单：
...
 while(target_index < token_length && pattern_index < pattern_length) {
  if(target[target_index] == pattern[pattern_index]|| pattern[pattern_index] == '?') {
   target_index++;
   pattern_index++;
  } else {
...
建立失效函数的过程和匹配过程类似，修改如下：
...
 for(i = 1; i < s; i++) {
  if(pattern[i] == pattern[array[i - 1]]|| pattern[i] == '?' || pattern[array[i - 1]] == '?')
   array[i] = array[i - 1] + 1;
...

本质上，?并没有修改算法，而仅仅修改了匹配规则——遇到?则一定匹配。然而*与此不同，*的作用是匹配任意多个字符，显然我们不能简单的修改匹配过程而满足要求。如果我们重新思考*的作用，我们会发现*的另一个作用就是分割P串，即如果P=P₁*P₂，那么与其说*代表匹配任意多个字符，不如说P的匹配条件是在匹配P₁子串后再匹配P₂子串。

现在回顾失效函数的作用，如果当匹配到P的j+1位时匹配失败，那么重新开始匹配的时候，P串的位置调整到f(j)位，直到P串的位置调整到0，则匹配重新开始。但当P=P₁*P₂，假如P₁已经匹配成功，而在P₂中发生匹配失败，那么P串要需要调整位置，但P串无论如何调整，此时也不应该调整到0，最多调整到P₂的开始处，因为P₁已经匹配，只需匹配P₂即可。假如P=abcab*abcab，失效函数应该是（注意之前提到*的作用）：
a b c a b * a b c a b
0 0 0 1 2 - 6 6 6 7 8

因此，要想让KMP支持*，那么关键是要重新设计失效函数的建立算法，如下：
public void Build() {
 if(pattern == null)
  throw new Exception("KMP Exception : null pattern");
 array = new int[pattern.Length];
 int i = 0, s = pattern.Length;
 if(s > 1)
  array[0] = 0;
 int begin = 0;
 for(i = 1; i < s; i++) {
  if(pattern[i] == '*') {
   array[i] = i;
   begin = i + 1;
  } else if(pattern[i] == pattern[array[i - 1]] || pattern[i] == '?' || pattern[array[i - 1]] == '?')
   array[i] = array[i - 1] + 1;
  else
   array[i] = begin;
 }
} 

算法中begin表示每段字符串的开始位置。此外，匹配过程也应该进行相应的修改，因为字符*对于匹配没有任何帮助，它属于占位符，因此需要跳过，匹配算法如下：
public int Match(String target, int start) {
 if(array == null || pattern == null || target == null)
  return -1;
 int target_index = start;
 int pattern_index = 0;
 int token_length = target.Length;
 int pattern_length = pattern.Length;
 int begin = 0;
 while(target_index < token_length && pattern_index < pattern_length) {
  if(pattern[pattern_index] == '*') {
   begin = pattern_index + 1;
   pattern_index++;
  } else if(target[target_index] == pattern[pattern_index] || pattern[pattern_index] == '?') {
   target_index++;
   pattern_index++;
  } else {
   if(pattern_index == begin)
    target_index++;
   else
    pattern_index = array[pattern_index - 1];
  }
 }
 if(pattern_index == pattern_length)
  return target_index - pattern_length + begin;
 return -1;
}

5 正则语言和确定状态自动机

一个数字逻辑的问题：设计一个识别11011的电路，解这个问题的关键就是设计出这个电路的DFA，如下：

仔细看看这个状态机，是不是和KMP的算法有几分类似呢？这并不是巧合，因为KMP算法中的失效函数总可以等价的转化为一个DFA。当然KMP的DFA远比识别11011的DFA要复杂，原因在于KMP接受的输入是全体字符集合，识别11011的DFA只接受0和1这两个输入。我们知道，一个正则语言和一个DFA是等价的，而KMP计算失效函数的算法，实际上等价于求DFA的过程，f(j)的值实际上表明状态j+1接受到不正确的字符时应该回溯到的状态（注意此时输入流并没有前进）。普通的字符串都能看成是一个正则语言，含有通配符?和*的字符串也可以等价的转换为一个正则表达式。但是，正则语言的集合远比KMP算法所能支持的模式集合的更大，期间原因还是刚才提过的输入问题。试想P=p₁p₂...p_n，当匹配到p_j的时候，如果下一个输入字符正是p_j，那么状态机进入下一个状态，如果不是p_j，那么状态机按照实效函数的指示转移到状态f(j-1)，也就是说KMP状态机的每个状态只能根据输入是否为p_j来进行转移。而正则表达式所对应的状态机则有所不同，如果正则语言L=l₁l₂...l_n，假设这些都是字母，当匹配到l_j位的时候，如果下一个输入字符正是l_j，那么状态机进入下一个状态，否则它还可以根据输入的值进行转移，例如l_j=c₁时转换到状态x，l_j=c₂时状态转换到y等等。

6 结语

字符串匹配问题是老问题了，并没有太多新意可言，只不过虽然KMP算法十分简单，但它的内在含义还是十分深刻的。横向比较KMP、DFA和正则语言、正则表达式我们会发现，它们之间存在很多的关联，而这种比较也有利于我们更好的理解这些算法，或者改进这些算法。最后说一句，试图利用目前的框架使得KMP算法支持全部种类的通配符（对应于正则表达式就是x?、x*、x+、{m,n}等等）是不可能，而我们也不需要这么做，因为我们还有正则表达式嘛。