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