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 would feel more appreciated if you could offer me some explanation or Reference Material.
Thanks

give me your e-mail!

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!

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