kmpjava
kmp演算法
一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。
如今，大夥基本上都用嚴蔚敏老師的書，那我就以此來講解KMP演算法。(小弟正在備戰考研，為了節省時間，很多課本上的話我都在此省略了，以後一定補上。)
嚴老的《數據結構》79頁講了基本的匹配方法，這是基礎。先把這個搞懂了。
80頁在講KMP演算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認識。目的在於指出「由此，在整個匹配的過程中，i指針沒有回溯，」。
我們繼續往下看：
現在討論一般情況。
假設 主串：s: 『s(1) s(2) s(3) ……s(n)』 ; 模式串 ：p: 『p(1) p(2) p(3)…..p(m)』
把課本上的這一段看完後，繼續
現在我們假設 主串第i個字元與模式串的第j(j<=m)個字元『失配』後，主串第i個字元與模式串的第k(k<j)個字元繼續比較
此時，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我們得到關系式
『p(1) p(2) p(3)…..p(j-1)』 = 』 s(i-j+1)……s(i-1)』
由於s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：(k<j),
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(i-k+1)s(i-k+2)……s(i-1)』
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比較)
匹配串： P(1) p(2) …… p(k-1) p(k)
現在我們把前面總結的關系綜合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比較)
P(1) p(2) ……. p(k-1) p(k)
由上，我們得到關系：
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(j-k+1)s(j-k+2)……s(j-1)』
接下來看「反之，若模式串中存在滿足式(4-4)。。。。。。。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。(偽代碼)
K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
課本83頁不是有個例子嗎？就是 圖4.6
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
然後找幾道練習題好好練練，一定要做熟練了。現在你的腦子里已經有那個next演算法的初步思想了，再回去看它是怎麼推出來的，如果還看不懂，就繼續做練習，做完練習再看。相信自己！！！
附：
KMP演算法查找串S中含串P的個數count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //遞推計算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函數求T在主串S中的個數count的KMP演算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
補上個Pascal的KMP演算法源碼
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函數用於模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0
不再贅述演算法原理，下面是兩個函數，已經通過測試，可以直接用。
private int[] get_nextval(String t) {
int len = t.length();
int i = 0;
int j = -1;
int next[] = new int[len];
while (i < len - 1) {
if (j == -1 || (t.charAt(i) == (t.charAt(j)))) {
i++;
j++;
if (t.charAt(i) != (t.charAt(j))) {
next[i] = (j + 1);
} else {
next[i] = next[j];
}
} else {
j = (next[j] - 1);
}
}
return next;
}
private int index_KMP(String s, String t, int[] next) {
int i = 0;
int j = 0;
while (i < s.length() - 1 && j < t.length() - 1) {
if (j == 0 || (s.charAt(i) == t.charAt(j))) {
i++;
j++;
} else
j = (next[j] - 1);
}
if (j > t.length() - 2) {
return (i - t.length() + 1);
} else
return -1;
}
❷ java字元串最大長度
1.String內部是以char數組的形式存儲，數組的長度是int類型，那麼String允許的最大長度就是Integer.MAX_VALUE了,2147483647;
又由於java中的字元是以16位存儲的，因此大概需要4GB的內存才能存儲最大長度的字元串。所以，發送xml批量的需要在oracle資料庫中用clob類型，而在java 端可以用String；
2. ResultSet rs = st.executeQuery("select CLOBATTR from TESTCLOB where ID=1");
if (rs.next())
{
java.sql.Clob clob = rs.getClob("CLOBATTR");
inStream = clob.getCharacterStream();
char[] c = new char[(int) clob.length()];
inStream.read(c);
//data是讀出並需要返回的數據，類型是String
data = new String(c);
inStream.close();
}
inStream.close();
con.commit();
❸ KMP演算法詳細代碼
private int KMP(String inText, String inMode)
{
if (inText.Length < inMode.Length)
{
return -1;
}
int[] arrNext = new int[inMode.Length + 1];
this.Next(inMode, arrNext);
int i, j; // i是主串游標 j是模式串游標
for (i = j = 0; i < inText.Length && j < inMode.Length; )
{
if (j == -1 || // 模式串游標已經回退到第一個位置
inText[i] == inMode[j]) // 當前字元匹配成功
{ // 滿足以上兩種情況時兩個游標都要向前進一步
++i;
++j;
}
else // 匹配不成功,模式串游標回退到當前字元的arrNext值
{
j = arrNext[j];
}
}
if (j >= inMode.Length)
{
return i - inMode.Length;
}
else
{
return -1;
}
}
private void Next(String inMode, int[] arrNext)
{
arrNext[0] = -1;
for (int i = 0, j = -1; i < inMode.Length; )
{ // i是主串游標 j是模式串的游標
if (j == -1 || // 如果模式串游標已經回退到第一個字元
inMode[i] == inMode[j]) // 如果匹配成功
{ // 兩個游標都向前走一步
++i;
++j;
arrNext[i] = j; // 存放當前的arrNext值為此時模式串的游標值
}
else // 匹配不成功j就回退到上一個arrNext值
{
j = arrNext[j];
}
}
}
❹ 如何java讀取海量中文文本
使用Boyer-Moore演算法
或者使用KMP演算法
建議使用後者
KMP演算法（java）
public class KMP {
/**
* @param args
*/
//計算模式串的next值
public static void getNext(String strModel, int dNext[]){
int i = 0,j = 1;
dNext[1] = 0;
while(j < strModel.length()){
while(i > 0 && strModel.charAt(i) != strModel.charAt(j))//遞推
i = dNext[i];
i++;
j++;
if(j == strModel.length())
break;
if(strModel.charAt(j) == strModel.charAt(i))//得出next值
dNext[j] = dNext[i] + 1;
else
dNext[j] = i;
}
}
//利用next值查詢子串
public static int getSubString(String strMain, String strModel, int dStart){
int dPos = -1;
int i = dStart;
int j = 1;
int dNext[] = new int[200];
getNext(strModel, dNext);
while(i<strMain.length()){
if(strMain.charAt(i) == strModel.charAt(j)){//當前字元匹配
if(j == (strModel.length()-1)){//查找成功
dPos = i - j + 1;
break;
}
i++;
j++;
}
else{//當前字元不匹配
if(dNext[j] == 0){
i++;
j = 1;
}
else{
j = dNext[j];
}
}
}
return dPos;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String strModel = " jlsdjflskjdm";
int[] dNext = new int[20];
getNext(strModel, dNext);
for(int i = 1; i<strModel.length(); i++)
System.out.print(dNext[i] + " ");
String strMain = " ";
System.out.println();
System.out.println(getSubString(strMain, strModel, 1));
}
}
❺ 串的應用kmp演算法。求一個字元串在另一個字元串中第一次出現的位置。
KMP.java
源代碼為：
package algorithm.kmp;
/**
* KMP演算法的Java實現例子與測試、分析
* @author 崔衛兵
* @date 2009-3-25
*/
public class KMP {
/**
* 對子串加以預處理，從而找到匹配失敗時子串回退的位置
* 找到匹配失敗時的最合適的回退位置，而不是回退到子串的第一個字元，即可提高查找的效率
* 因此為了找到這個合適的位置，先對子串預處理，從而得到一個回退位置的數組
* @param B，待查找子串的char數組
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循環一次，就會找到一個回退位置
for(int i=1;i<size;i++){
//當找到第一個匹配的字元時，即j>0時才會執行這個循環
//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有當子串中含有重復字元時，回退的位置才會被優化
if(B[j]==B[i]){
j++;
}
//找到一個回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}
/**
* KMP實現
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//當找到第一個匹配的字元時，即j>0時才會執行這個循環
//或者說p2中的j++會在p1之前執行（限於第一次執行的條件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合適的回退位置
j=P[j-1];
}
//p2 找到一個匹配的字元
if(B[j]==A[i]){
j++;
}
//輸出匹配結果，並且讓比較繼續下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}
public static void main(String[] args) {
//回退位置數組為P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!這個會匹配1次","abcdef");
//回退位置數組為P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!這個會匹配2次","ititit");
//回退位置數組為P[0, 0, 0]
kmp("測試漢字的匹配，崔衛兵。這個會匹配1次","崔衛兵");
//回退位置數組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("這個會匹配0次","it1it1it1");
}
}
❻ java String類封裝的index方法是用的KMP匹配嗎
是採用KMP方式匹配的，這是indexOf的實現代碼
public int indexOf(int ch, int fromIndex) {
int max = offset + count;
char v[] = value;
if (fromIndex < 0) {
fromIndex = 0;
} else if (fromIndex >= count) {
// Note: fromIndex might be near -1>>>1.
return -1;
}
int i = offset + fromIndex;
if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
// handle most cases here (ch is a BMP code point or a
// negative value (invalid code point))
for (; i < max ; i++) {
if (v[i] == ch) {
return i - offset;
}
}
return -1;
}
if (ch <= Character.MAX_CODE_POINT) {
// handle supplementary characters here
char[] surrogates = Character.toChars(ch);
for (; i < max; i++) {
if (v[i] == surrogates[0]) {
if (i + 1 == max) {
break;
}
if (v[i+1] == surrogates[1]) {
return i - offset;
}
}
}
}
return -1;
}
你可以看到是放到一個char數組中一個個匹配的。
❼ Java編程實現字元串的模式匹配
傳統的字元串模式匹配演算法（也就是BF演算法）就是對於主串和模式串雙雙自左向右，一個一個字元比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的演算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。
KMP 演算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt演算法，簡稱KMP演算法。KMP演算法是字元串模式匹配中的經典演算法。和BF演算法相比，KMP演算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得演算法時間復雜度只為O（n＋m）。
❽ java中String的int indexof(String)方法是用什麼演算法實現的，是KMP嗎
不是KMP演算法，自己看看源碼就知道了。
至於原因:
KMP對特殊的字元串比較好用 就是自身帶有很多重復子串的那種
在字元串不長的情況下 KMP比較耗時
❾ Java查找一個字元串中包含某個字元串的速度最快的方法
用正則，至於快不快，反正我認為很快
import java.util.regex.*;
public class Regex {
public static void main(String[] args) {
String str = "My Heart Will Go On!";
Pattern p = Pattern.compile("Will");
Matcher m = p.matcher(str);
while (m.find()) {
System.out.println("包含這個字元串！");
}
}
}