Loading...
Please wait, while we are loading the content...
Similar Documents
Centroid Trees with Appli ation to String Pro essing
| Content Provider | Semantic Scholar |
|---|---|
| Author | Shin, Dong-Guk |
| Copyright Year | 2018 |
| Abstract | Abstra t. A entroid of a tree T is a node v whi h minimizes over all nodes the largest onne ted omponent of T indu ed by removing v from T . A entroid tree U of another tree T is de ned on the same set of nodes of T : the root v of U is a entroid of T and the subtrees of v (in U) are the entroid trees of the onne ted omponents of T v. We des ribe some interesting properties of the entroid and of the entroid tree. Our linear algorithm to nd a entroid of a tree improves on the previously known algorithms either in terms of spa e requirement or in terms of time requirement. From the algorithm for nding a entroid it is easy to obtain an O(n log n) time algorithm to onstru t a entroid tree of a given tree with n nodes. However, we do not know whether this is the best that one an a hieve. By exploiting the properties of the entroid tree, we devise an eÆ ient algorithm for the longest ommon substring problem (LCS). Given two strings S (the text) of length n and P (the pattern) of length m, the LCS problem is to nd the longest substring that appears in both the text and the pattern. Our algorithm requires O(n logn) time and O(n) spa e to prepro ess the text. After prepro essing of the text, the algorithm takes O(m log n) time using O(m) extra spa e to nd the solution. The algorithm may be used in the DNA appli ations in whi h the text is very large and xed and is to be sear hed with many di erent patterns (n m). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.stringology.org/cgi-bin/getfile.cgi?c=-&n=5&t=pdf&y=1999 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
