|
|
вернуться в форумI find many solutions are less than 1 second. Could any one give me some hint to improve efficiency. Thanks in advance. I think that solutions which runs less than 1 sec. use hash table! How to construct Hash Table. If use substring of each command as the key, construction may consume too much time. to construct all substrings we need O(N*MaxLen^2) it is enough here! I solved it without hash table,that is why my solution works more than 1 sec. Edited by author 25.10.2009 00:35 What is mean of "MaxLen". Does it mean max command string length? Yes! it is 100! oh If more than one command string have same substring. Do you consider it as same key value. Read statement! it is clear to understand it yourself! Thanks. Actually, I could not find clear connection between Hash Table and this problem. Look at previous post, there is another solution, without hash table! I am a new beginner on this website. Could I get algorithm rationale of solution posted by other programmers? if yes, How? How aboult test data. Where can I get? You could look at Statistics of each problem! You couldn't get test data. You could create your own, and somebody will answer on it! I would feel more appreciated if you could offer me some explanation or Reference Material. Thanks give me your e-mail! email: glbian@yahoo.com.cn MSN: glbian@live.com Thanks for your help. Interesting!? N*M*M~5 000 000 substring Let most of them are bad (or having equal copy). For equal string hash is equal and each bad substring must be compared at whole length ~ 50 with something. Thus we have 250 000 000 operations. I think that successful authors applied some string compressing. Hash with binary search - AC in 1.5 sec without whole-length comparing strings with equal hash |
|
|