Name
Abstract | ||
|---|---|---|
A word of the form WW for some word (Win varSigma ^*) is called a square, where (varSigma ) is an alphabet. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol Open image in new window which matches (agrees with) any symbol from Open image in new window . A p-square is a partial word matching at least one square WW without holes. Two p-squares are called equivalent if they match the same set of squares. We denote by ( psquares (T)) the number of non-equivalent p-squares which are factors of a partial word T. Let (mathrm {PSQUARES}_k(n)) be the maximum value of ( psquares (T)) over all partial words of length n with at most k holes. We show asymptotically tight bounds: $$ c_1cdot min (nk^2,, n^2) le mathrm {PSQUARES}_k(n) le c_2cdot min (nk^2,, n^2) $$for some constants (c_1,c_2u003e0). We also present an algorithm that computes ( psquares (T)) in (mathcal {O}(nk^3)) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for (k=mathcal {O}(1)) and its time complexity near-matches the maximum number of non-equivalent p-square factors in a partial word. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-319-62389-4_9 | COCOON |
Keywords | DocType | Volume |
Partial word, Square in a word, Approximate period, Lyndon word | Journal | 37 |
Issue | ISSN | Citations |
2 | 1573-2886 | 0 |
PageRank | References | Authors |
0.34 | 14 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 3 | 4.12 |
| Maxime Crochemore | 2 | 2655 | 281.75 |
| Costas S. Iliopoulos | 3 | 0 | 1.35 |
| Tomasz Kociumaka | 4 | 217 | 38.57 |
| Solon P. Pissis | 5 | 281 | 57.09 |
| Jakub Radoszewski | 6 | 624 | 50.36 |
| wojciech rytter | 7 | 130 | 17.13 |
| Tomasz Waleń | 8 | 706 | 39.62 |