one question about algorithm - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

one question about algorithm

one question about algorithm# Programming - 葵花宝典

c*g2007-10-15 07:10

1 楼

given one article, and a set of keywords
find the shortest length part which contain all the keywords
how to do that?
After translated, it will be: given a sequence, how to
find a shortest substring that contains all the items required. Example: a s
equence "abaccdefgacel" and a set of key words "a" "c", "d" and "e". The sho
rtest substring contianing all of the key words is "accde". Find one of such
shortest substrings.

j*e2007-10-15 07:10

2 楼

Let me try:
step 1: traverse the string once, and count the occurance of each key
characters in the search string: i.e. a:3, c:3, d:1, e:1
step 2 : Recursion
/*"count" maps key characters to the # of occurance*/
/*"stringPath" is the longest string path so far containing all key characters
*/
void checkShortest(deque& stringPath, Map& count)
{
char head = stringPath.front();
char tail = stringPath.back();
/*Head character is not a key character*/
/*Or it is a key character, and h

s*u2007-10-15 07:10

3 楼

are你sure就是一个字母的key？
而且看不懂你的什么意思 -_-

characters

【在 j********e 的大作中提到】

: Let me try:
: step 1: traverse the string once, and count the occurance of each key
: characters in the search string: i.e. a:3, c:3, d:1, e:1
: step 2 : Recursion
: /*"count" maps key characters to the # of occurance*/
: /*"stringPath" is the longest string path so far containing all key characters
: */
: void checkShortest(deque& stringPath, Map& count)
: {
: char head = stringPath.front();

j*e2007-10-15 07:10

4 楼

I just worked off the simplified example in the original post. For string
keyword, the same token applies.

【在 s****u 的大作中提到】

: are你sure就是一个字母的key？
: 而且看不懂你的什么意思 -_-
:
: characters

s*02007-10-15 07:10

5 楼

Definition: for single keyword X(consists of one or more characters),
*f_start1(X)
means the earliest poistion of the first character of X in the article.
*f_end1(X)
means the latest position of the first character of X in the article.
*f_start2(X)
means the earliest poistion of the last character of X in the article.
*f_end2(X)
means the latest position of the last character of X in the article.
For n keywords X1,X2,X3...,Xn, suppose the starting and ending position
of the shortest sub-article

i*r2007-10-15 07:10

6 楼

One solution: O(N) time complexity
str is the input string,
K is the set of characters to be covered.
1. Create a structure to remember best result
Create a solution set R, which includes 0 solution.
A solution includes: a) starting index b) a bitmap showing which
characters are already covered.
2. scan through the string, for every character ch (with index = i)
2.1 if ch is not in K, do nothing and move on
2.2 if ch is in K, initialize a solution and put in R
s.index = i, ch

s*u2007-10-15 07:10

7 楼

ft，character的key的话，简单的贪心就可以O(n)

【在 i********r 的大作中提到】

: One solution: O(N) time complexity
: str is the input string,
: K is the set of characters to be covered.
: 1. Create a structure to remember best result
: Create a solution set R, which includes 0 solution.
: A solution includes: a) starting index b) a bitmap showing which
: characters are already covered.
: 2. scan through the string, for every character ch (with index = i)
: 2.1 if ch is not in K, do nothing and move on
: 2.2 if ch is in K, initialize a solution and put in R