It seems that the algorithms are O(Nk) where N is size of document and
k is number of keywords needed. So this means if you are looking for a
N/2 words in a document of length N, the worst case will actually be
O(N^2). Not something that you'll get from a google query, but still
possible for this
Yes!
Look here there is a program:
http://groups.google.com/group/algogeeks/browse_thread/thread/11b032a28995baed/7b896ee015b090e5
On Feb 13, 3:16 am, conundrum <[EMAIL PROTECTED]> wrote:
> Given a text and a set of keywords, is there a linear time algorithm
> to find the smallest subtext contain
oh, even this one will fail :) this will find the smallest subtext up
to the first occurrence of the event that all the keyword are found.
e.g A A A B B A A C A B C will report B A A C as smallest subtext but
A B C is the smallest subtext.
--~--~-~--~~~---~--~~
Yo
Yes Dave, you are right.
I hope algorithm below will work.
maintain a hash table with keys as the set of keywords and values as a
boolean value initialized with false.
initialize a counter count with 0
let n be the total number of keywords.
word = 1st word of the text
while( word )
{
stack1.push
This algorithm won't find the smallest subtext. Suppose the keywords
are A B and C and the text is A A B A C. The algorithm will report the
entire text as the subtext, but the correct answer is B A C.
Dave
On Feb 13, 3:46 am, arun <[EMAIL PROTECTED]> wrote:
> maintain a hash table with keys as t
maintain a hash table with keys as the set of keywords and values as a
boolean value initialized with false.
initialize a counter count with 0
let n be the total number of keywords.
start comparing the words of the text with keywords.
If word matches with keyword then
{
go to hash table and
if va
