java模式匹配演算法

『壹』 java正則表達式，matcher.find和 matcher.matches的區別

1.find()方法是部分匹配，是查找輸入串中與模式匹配的子串，如果該匹配的串有組還可以使用group()函數。
matches()是全部匹配，是將整個輸入串與模式匹配，如果要驗證一個輸入的數據是否為數字類型或其他類型，一般要用matches()。

2.Pattern pattern= Pattern.compile(".*?,(.*)");
Matcher matcher = pattern.matcher(result);
if (matcher.find()) {
return matcher.group(1);
}

3.詳解：
matches
public static boolean matches(String regex, CharSequence input)
編譯給定正則表達式並嘗試將給定輸入與其匹配。
調用此便捷方法的形式
Pattern.matches(regex, input);
Pattern.compile(regex).matcher(input).matches() ;
如果要多次使用一種模式，編譯一次後重用此模式比每次都調用此方法效率更高。
參數：
regex - 要編譯的表達式
input - 要匹配的字元序列
拋出：
PatternSyntaxException - 如果表達式的語法無效

find
public boolean find()嘗試查找與該模式匹配的輸入序列的下一個子序列。
此方法從匹配器區域的開頭開始，如果該方法的前一次調用成功了並且從那時開始匹配器沒有被重置，則從以前匹配操作沒有匹配的第一個字元開始。
如果匹配成功，則可以通過 start、end 和 group 方法獲取更多信息。
matcher.start() 返回匹配到的子字元串在字元串中的索引位置.
matcher.end()返回匹配到的子字元串的最後一個字元在字元串中的索引位置.
matcher.group()返回匹配到的子字元串
返回：
當且僅當輸入序列的子序列匹配此匹配器的模式時才返回 true。

『貳』 JAVA正則表達式，matcher.find和 matcher.matches的區別

find()方法是部分匹配，是查找輸入串中與模式匹配的子串，如果該匹配的串有組還可以使用group()函數。
matches()是全部匹配，是將整個輸入串與模式匹配，如果要驗證一個輸入的數據是否為數字類型或其他類型，一般要用matches()。

『叄』 java kmp演算法中的 kmp 是什麼意思

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正則表達式怎麼匹配所有符合要求的子字元串

正則有貪婪和非貪婪模式，所以你的最後集合只會有這兩種的數據，不會出現如：zobo，boco。
代碼片段：

Pattern pattern = Pattern.compile(".*?o");
Matcher matcher = pattern.matcher("zoboco");

while(matcher.find()){
String e=matcher.group(0);
System.out.println(e);
}

運行結果：

zo
bo
co
你可以通過這些結果按順序排列組合出想要的組合數據如：zobo,boco,zoboco
關於java正則表達式的語法可以參考：java正則表達式語法詳解及其使用代碼實例
搜索"正則"的分享列表

『伍』 java 正則表達式matcher.group()匹配多種結果的規則

這是由正則表達式的匹配策略所導致的，如果想要得到多個小的匹配結果你需要將正則表達式改為:

Stringreg="乘+(.*?)+車";

即可得到想要的結果：

具體原理你可以查看這個鏈接:http://blog.csdn.net/luoweifu/article/details/42759439 講的很詳細

『陸』 java中string.matcher(regex)如何指定匹配模式, 即要實現和js中的/i/m/g等等的功能

應該是想實現不管大小寫的a-z和1-9的組合吧，String regex="[a-zA-Z][0-9]"即可，上面的只能識別兩個字元，如果想要多個字元匹配，那麼加在後面加*表示零次或者多次，加+表示一次或者多次，像上面的情況，1.如果要匹配「adfj123」就用[a-zA-Z]+[0-9]+即可；2.如果字母出現一次，數字出現很多，那麼就用[a-zA-Z]([0-9])+，如「a123」；3.如果字母出現一次，數字出現0次或者多次，就用
[a-zA-Z]([0-9])*即可；4.如果字母出現0次或者多次，數字出現一次就用[a-zA-Z]*([0-9])，這些是最常用的，樓主可以看看api在java.util.regex.pattern