r**t 发帖数: 937 | 1 想知道两个正规表达式有没有交集(只要知道有没有,不要知道交集是什么)
例如,正规表达式
^abc/.*\\z (abc开始的string)
和
^.*ef\\z (ef结尾的string)
有交集;
和
^ef/.*\\z (ef开始的string)就没有
应该怎么做呢? |
S*O 发帖数: 52 | 2 this has nothing to do w/ java bah. more like an algorithm...
【在 r**t 的大作中提到】 : 想知道两个正规表达式有没有交集(只要知道有没有,不要知道交集是什么) : 例如,正规表达式 : ^abc/.*\\z (abc开始的string) : 和 : ^.*ef\\z (ef结尾的string) : 有交集; : 和 : ^ef/.*\\z (ef开始的string)就没有 : 应该怎么做呢?
|
g*s 发帖数: 2277 | 3 OP meant how to do this with Java reg exp package ya(if Java reg exp package
implemented this).
【在 S*O 的大作中提到】 : this has nothing to do w/ java bah. more like an algorithm...
|
S*O 发帖数: 52 | 4 if so, then use reg1 to match the objects, w/ the matched result,
run reg2, if there are any matches, that means these 2 reg has intersection.
otherwise no.
that would work bah?
【在 g*s 的大作中提到】 : OP meant how to do this with Java reg exp package ya(if Java reg exp package : implemented this).
|
R*******r 发帖数: 104 | 5 How do you create the strings? you only have reg expressions.
【在 S*O 的大作中提到】 : if so, then use reg1 to match the objects, w/ the matched result, : run reg2, if there are any matches, that means these 2 reg has intersection. : otherwise no. : that would work bah?
|
S*O 发帖数: 52 | 6 sth like this:
public static boolean hasIntersection(string pattern1, String pattern2,
String[] strings) {
RE reg1 = new RE(pattern1);
RE reg2 - new RE(pattern2);
for (int i=0;i
if(reg1.isMatch(strings[i]))
if(reg2.isMatch(strings[i])
return true;
return false;
}
【在 S*O 的大作中提到】 : if so, then use reg1 to match the objects, w/ the matched result, : run reg2, if there are any matches, that means these 2 reg has intersection. : otherwise no. : that would work bah?
|
S*O 发帖数: 52 | 7 what strings?
【在 R*******r 的大作中提到】 : How do you create the strings? you only have reg expressions.
|
g*s 发帖数: 2277 | 8 reg1-matched strings are infinite ya...
【在 S*O 的大作中提到】 : if so, then use reg1 to match the objects, w/ the matched result, : run reg2, if there are any matches, that means these 2 reg has intersection. : otherwise no. : that would work bah?
|
g*s 发帖数: 2277 | 9 not check whether to have intersection on some string set, but universal
string set ya.
【在 S*O 的大作中提到】 : sth like this: : public static boolean hasIntersection(string pattern1, String pattern2, : String[] strings) { : RE reg1 = new RE(pattern1); : RE reg2 - new RE(pattern2); : for (int i=0;i: if(reg1.isMatch(strings[i])) : if(reg2.isMatch(strings[i]) : return true; : return false;
|
S*O 发帖数: 52 | 10 oh, i see...
when there is no target-to-be-matched, how to find out 2 expressions
have intersection or not...
hmmmmm
【在 g*s 的大作中提到】 : reg1-matched strings are infinite ya...
|
|
|
S*O 发帖数: 52 | 11 then the question is if there is a way to
join multiple regular expression patterns...
if u can join them together, then u know if they intersect or not.
【在 S*O 的大作中提到】 : oh, i see... : when there is no target-to-be-matched, how to find out 2 expressions : have intersection or not... : hmmmmm
|
w*****e 发帖数: 23 | 12 Regex can be turned into finite state (If I am wrong, please point out). You
can turn them into 2 state machines (FSM), and try to minimize those states.
If Minimize FSM is same, then they are match, otherwise not.
You can find algorithm by search google about Minimize FSM.
best regard
【在 S*O 的大作中提到】 : then the question is if there is a way to : join multiple regular expression patterns... : if u can join them together, then u know if they intersect or not.
|
c****r 发帖数: 185 | 13 直接求交集的忘了有没有,
下面是变通的办法:
先各自求补集,然后求并集,再对并集取补。
求补集:把FA的所有接受状态变成非接受状态,非接受状态(包括死状态)变成接
受状态。
求并集:R1|R2
【在 r**t 的大作中提到】 : 想知道两个正规表达式有没有交集(只要知道有没有,不要知道交集是什么) : 例如,正规表达式 : ^abc/.*\\z (abc开始的string) : 和 : ^.*ef\\z (ef结尾的string) : 有交集; : 和 : ^ef/.*\\z (ef开始的string)就没有 : 应该怎么做呢?
|
r**t 发帖数: 937 | 14 多谢各位帮忙,看来能想到的办法还是通过automata。不过俺本来是想偷懒用java
现成的东西,现在看来是没有了。只好自己吭嗤吭嗤写了,sigh~~
【在 c****r 的大作中提到】 : 直接求交集的忘了有没有, : 下面是变通的办法: : 先各自求补集,然后求并集,再对并集取补。 : 求补集:把FA的所有接受状态变成非接受状态,非接受状态(包括死状态)变成接 : 受状态。 : 求并集:R1|R2
|
d**u 发帖数: 412 | 15 有现成的java package的.
http://regex.info/java.html
【在 r**t 的大作中提到】 : 多谢各位帮忙,看来能想到的办法还是通过automata。不过俺本来是想偷懒用java : 现成的东西,现在看来是没有了。只好自己吭嗤吭嗤写了,sigh~~
|