首页 > ACM题库 > HDU-杭电 > hdu 4581 Microblog Subscription待解决[解题报告]C++
2015
09-17

hdu 4581 Microblog Subscription待解决[解题报告]C++

Microblog Subscription

问题描述 :

Jia Baoyu was the best programmer in his big family―the Family of Jia, which is why he was regarded as the most charming gentleman among girls. Recently he was designing a new microblog to target the requirements of sharing information in his family. In his system, a microblog can be regarded as a document contains no more than 2000 words.
By asked to other member’s in the Family of Jia, he decided to release a function of “subscription” in his microblog. Let’s describe this function more specifically:
A user can submit a query to describe subscription requirement. A query contains a match type, a match distance constraint and a set of not more than 5 English words. After the user submitted the query, he/she will receive all the new microblog that satisfies the query in his/her “Feeds stream”. If a microblog satisfies a query, it should match all the words in the query. And a microblog matches a word X when there is at least a word in microblog that matches the word X. Note that the match constraint is applied independently for each word in the query.
There are three types of word matching: exact match, approximate match under a Hamming distance constraint and approximate match under an edit distance. The definitions of these three matches is are follows:
Exact match: two words are exactly the same;
Approximate match under Hamming distance D constraint:two words with the same length have at most D positions at which corresponding letters are different.
Approximate match under edit distance D constraint:one word can be changed into the other word in at most D single-letter edits, including insertion, deletion and substitution.
For example, Lin Daiyu submitted a query: edit distance match with distance 1, and the word set “flower poem tear”. Then she will receive the microblog “I wrote a pom full of tears after I saw Daiyu buried the flowers”. In this case, “flower” can be matched with “flowers” in 1 edit distance, “tear” can be matched with “tears” and “poem” can be matched with “pom” (obviously it was a typo).
After a user submitted a query, he/she could delete the query in anytime. After that he/she would not receive microblogs that satisfy this query.
Now please help Jia Baoyu to accomplish this function.

输入:

The first line of input file contains an integer representing the following number of lines.
Each of the following line has three formats:
s [id] [type] [dist] [k] [word_1] [word_2] … [word_k]
The line that starts with lowercase ‘s’ means adding a query into system. [id] is an integer between 1 to 1000 representing the id of the query. [type] is an integer between 0 to 2 representing the match type (0 means exact match, 1 means hamming distance match and 2 means edit distance match). [dist] is an integer representing the distance constraint (Note that the distance is always 0 for exact match). This distance constraint is at most 2. [k] means the number of following words (0<k<=5). [word_i] represents a word in this query. All the items are separated by a space.
e [id]
The line that starts with lowercase ‘e’ means deleting a query from system. [id] is the id of that query. We guarantee that the id always exist and has not deleted before.
m [id] [k] [word_1] [word_2] … [word_k]
The line that starts with lowercase ‘m’ means a microblog. [id] is an integer between 1 to 100 which means the id of the microblog. [k] is an integer meaning the number of words that follows (0<k<=2000). [word_i] represents a word in this microblog. All the items are separated by a space.
The length of a word is less than or equal to 30, and there are no blanks in a word. The number of total queries is less than or equal to 1000, while the number of total microblogs is less than or equal to 100.

输出:

The first line of input file contains an integer representing the following number of lines.
Each of the following line has three formats:
s [id] [type] [dist] [k] [word_1] [word_2] … [word_k]
The line that starts with lowercase ‘s’ means adding a query into system. [id] is an integer between 1 to 1000 representing the id of the query. [type] is an integer between 0 to 2 representing the match type (0 means exact match, 1 means hamming distance match and 2 means edit distance match). [dist] is an integer representing the distance constraint (Note that the distance is always 0 for exact match). This distance constraint is at most 2. [k] means the number of following words (0<k<=5). [word_i] represents a word in this query. All the items are separated by a space.
e [id]
The line that starts with lowercase ‘e’ means deleting a query from system. [id] is the id of that query. We guarantee that the id always exist and has not deleted before.
m [id] [k] [word_1] [word_2] … [word_k]
The line that starts with lowercase ‘m’ means a microblog. [id] is an integer between 1 to 100 which means the id of the microblog. [k] is an integer meaning the number of words that follows (0<k<=2000). [word_i] represents a word in this microblog. All the items are separated by a space.
The length of a word is less than or equal to 30, and there are no blanks in a word. The number of total queries is less than or equal to 1000, while the number of total microblogs is less than or equal to 100.

样例输入:

6
s 1 1 2 1 bkple
m 2 1 apple
s 2 0 0 2 apple banana
m 1 2 apple banana
e 1
m 3 2 apple banana

样例输出:

2 1 1
1 2 1 2
3 1 2