Microblog Subscription
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 48 Accepted Submission(s): 8
Problem Description
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.
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.
Input
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.
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.
Output
For each microblog in the input file, output all the matched active queries when it published. The “active” means that query has been submitted and not deleted yet. The format is:
[id] [k] [q_1] [q_2] … [q_k]
[id] means the id of this microblog. [k] means the number of queries that it satisfies. [q_i] means a query id. Query ids must be sorted increasingly.
The order of microblog in output file must be the same as it is displayed in the input file.
[id] [k] [q_1] [q_2] … [q_k]
[id] means the id of this microblog. [k] means the number of queries that it satisfies. [q_i] means a query id. Query ids must be sorted increasingly.
The order of microblog in output file must be the same as it is displayed in the input file.
Sample Input
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
Sample Output
2 1 1 1 2 1 2 3 1 2