一，安裝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}等等）是不可能，而我們也不需要這么做，因為我們還有正則表達式嘛。