首页 > ACM题库 > HDU-杭电 > hdu 3643 Boolean String Expression待解决[解题报告]C++
2014
11-30

hdu 3643 Boolean String Expression待解决[解题报告]C++

Boolean String Expression

问题描述 :

Mike needs a bike and he decides to buy a second-hand one to save money. Luckily, he has found a second-hand goods BBS. However, there are so many messages there and it will be extremely boring for him to look through all those messages and figure out which one contains the information he needs. So he decides to write a program to do this.

The problem is: how to determine whether a message is about selling a bike. Mike decides to use a keyword-find-based algorithm. First choose some keywords and then the program checks whether a message contains these keywords or not. For example, he wants to find messages that contain ‘bike’,and at the same time have ‘sell’ or don’t have ‘buy’ ("bike on sell", "bike", "sell bike and buy …"are all what he needs, but "buy bike" is not). Of course he wants his program can be used to handle things more than buying a bike.

As the string matching nature of the keyword-find-based algorithm, regular expression should be quite suitable here. But after a second thought, he throws it away: he even can’t figure out what the corresponding regular expression is for a simple query "don’t have the word ‘buy’".

After further thinking of this problem, Mike comes up with a great idea: combining string matching with Boolean algebra! He names it as "Boolean String Expression".

Formally, a Boolean String Expression is composed of normal strings, ‘&’(and), ‘|’(or) and ‘!’(not). A Boolean String Expression s matches a message M when:
1. s is a normal string, and it’s a substring of M
2. s = a & b, a and b are both Boolean String Expressions that match M
3. s = a | b, a and b are both Boolean String Expressions, and at least one of them matches M
4. s = ! a, a is Boolean String Expression which doesn’t match M

Precedence of the three operators is: ‘!’ > ‘&’ > ‘|’. And parenthesis can be used to change precedence of operators. Mike’s query can be easily expressed as:
bike & (sell | !buy)
Mike is very satisfied with this solution, but he comes to another problem: nearly all expressions can be changed into another form with the same meaning. For example, "bike & (sell | !buy)" has a equivalent form of:
(bike & sell) | (bike & !buy)
It may seem to be obvious to you. However, it confuses Mike a lot and he needs your help to write a problem to check whether two Boolean String Expressions are equivalent. (Equivalent here means: all messages that match one expression will match the other, all messages that don’t match one expression will not match the other too)

输入:

The first line contains an integer indicating the number of test cases (<=30).
Each test case contains three lines: The first line is an alphabet that contains only lower case letters. Suppose all messages we care about are only composed of those letters. The second line and 3rd line are two Boolean String Expressions. The expression contains only characters from the alphabet and ‘&’, ‘|’, ‘!’ , and its length is no more than 20.

输出:

The first line contains an integer indicating the number of test cases (<=30).
Each test case contains three lines: The first line is an alphabet that contains only lower case letters. Suppose all messages we care about are only composed of those letters. The second line and 3rd line are two Boolean String Expressions. The expression contains only characters from the alphabet and ‘&’, ‘|’, ‘!’ , and its length is no more than 20.

样例输入:

4
abcdefghijklmnopqrstuvwxyz
bike&(sell|!buy)
bike&sell|bike&!buy
abc
a&(b|c)
a&b|c
ab
ab&!a
ab&!b
ab
a|b
a|!a

样例输出:

Yes
No
Yes
No

Hint
Case 3: Both expressions match nothing, so they are equivalent. Case 4: Both expressions match all non-empty messages. However, the second expression can match an empty message, while the first one can’t.


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false