> No, I am not trying to do that at all. The trie is built to contain > only keywords. It can then be used to answer the question for the > current character 'Is this character part of a candidate keyword?' and > do this O(1). Candidate keywords are identified initially by the trei > root returning a reference to the node representing the first > character of the keyword rather than a null. (or, if you prefer, the > node linked to the root by that character's edge)
I see. This is some kind of data structure that I don't know. > Calm down. I am not asserting or even suggesting that your algorithm > does not find the shortest subsequence in all cases. Forget the nested > loop. A subsequence start pointer is needed and it is probably > irrelevant whether this is updated in the main loop or a sub-loop. > > However, compiling and running the listing I got output shown below > with initial complete sequence added, subsequences offset to align, > and subsequence sizes etc. omitted: > > abrebbqbcdfagbasdfbbaggqqebbcg--324c > abrebbqbc > bcdfa > cdfagb > cdfagba > cdfagbasdfb > cdfagbasdfbb > cdfagbasdfbba > cdfagbasdfbbaggqqeb > cdfagbasdfbbaggqqebb > aggqqebbc > aggqqebbcg--324c > The shortest subsequence is: range size: 5 [bcdfa] > > This is what I meant by longer and longer subsequences. For example, > once the subsequence cdfagb has been identified it is then impossible > that a shorter subsequence exists that starts with the same word 'c' > at the same location in the complete sequence. Logically the next > possible shorter subsequence starts with the next word 'a'. Checks > (result.size() > range.size()) on other 'c' start subsequences are > redundant. Very impressive! I spent half an hour at most on that program, and didn't thought about it deeply. Obviously you are better expert in it. :) > > Thank you for asking. I was not going to spend time on this if nobody > was interested. I will make a start this evening and make sure there > is sufficient debug output that you all can criticise it without > ploughing through the source code. > It's certainly not worth spending time on it if you don't want. I just wanted to see trei. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
