Thursday, October 18, 2012

Suffix Tree - Common pattern in 'N' strings

Given 'n' number of strings, find the common pattern among all of them in O(N) time.
For e.g. "sparrows", "tomorrow", "borrower". In the above 3 strings, the common pattern is "rrow".
Problems like this can be solved in linear time. The main point to note it is, this can be achieved at the cost of additional space. Searching will be linear time.


No comments:

Post a Comment