| Autor: |
Alzamel, Mai, Crochemore, Maxime, Iliopoulos, Costas S., Kociumaka, Tomasz, Radoszewski, Jakub, Rytter, Wojciech, Straszyński, Juliusz, Waleń, Tomasz, Zuba, Wiktor |
| Rok vydání: |
2019 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings $S$ and $T$ of length $n$, we are to compute the longest factor of $S$ whose cyclic shift occurs as a factor of $T$. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in $O(n \log^5 n)$ time. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
