Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 2

The DOI matches its Crossref record.

Linear-Time Computation of Local Periods

Duval, Jean-Pierre, Kolpakov, Roman, Kucherov, Gregory, Lecroq, Thierry, Lefebvre, Arnaud·2003·Lecture Notes in Computer Science
DOI 10.1007/978-3-540-45138-9_33
Open this paper in CoChat — free account

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/978-3-540-45138-9_33

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 24

  1. Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of the ACM 20, 762–772 (1977) · DOI · Paper page
  2. Choffrut, C., Karhumäki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook on Formal Languages, vol. I, pp. 329–438. Springer, Heidelberg (1997) · DOI
  3. Crochemore, M., Perrin, D.: Two-way string matching. J. ACM 38, 651–675 (1991) · doi:10.1145/116825.116845
  4. Crochemore, M., Rytter, W.: Text algorithms. Oxford University Press, Oxford (1994)
  5. Crochemore, M., Rytter, W.: Squares, cubes, and time-space efficient string searching. Algorithmica 13, 405–425 (1995) · DOI
  6. Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Information Processing Letters 12, 244–250 (1981) · DOI
  7. Crochemore, M.: Recherche linéaire d’un carré dans un mot. Comptes Rendus Acad. Sci. Paris Sér. I Math. 296, 781–784 (1983)
  8. Duval, J.-P., Mignosi, F., Restivo, A.: Recurrence and periodicity in infinite words from local periods. Theoretical Computer Science 262(1), 269–284 (2001) · doi:10.1016/s0304-3975(00)00204-8
  9. Duval, J.-P.: Périodes locales et propagation de périodes dans un mot. Theoretical Computer Science 204(1-2), 87–98 (1998) · doi:10.1016/s0304-3975(98)00033-4
  10. Guibas, L.J., Odlyzko, A.M.: Periods in strings. Journal of Combinatorial Theory, Series A 30, 19–42 (1981) · doi:10.1016/0097-3165(81)90038-8
  11. Galil, Z., Seiferas, J.: Time-space optimal string matching. Journal of Computer and System Sciences 26(3), 280–294 (1983) · doi:10.1016/0022-0000(83)90002-8
  12. Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997) · DOI · Paper page
  13. Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proc. of FOCS 1999, pp. 596–604. IEEE Comp. Soc., New York (1999)
  14. Kolpakov, R., Kucherov, G.: Finding repeats with fixed gap. In: Proc. of the 7th SPIRE, La Coruña, Spain, pp. 162–168. IEEE, Los Alamitos (2000)
  15. Kolpakov, R., Kucherov, G.: Finding approximate repetitions under hamming distance. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 170–181. Springer, Heidelberg (2001) · doi:10.1007/3-540-44676-1_14
  16. Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal of Computing 6, 323–350 (1977) · DOI · Paper page
  17. Kosaraju, S.R.: Computation of squares in string. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol. 807, pp. 146–150. Springer, Heidelberg (1994) · DOI · Paper page
  18. Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 17. Addison Wesley, Reading (1983)
  19. Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002) · DOI
  20. Main, M.G.: Detecting leftmost maximal periodicities. Discrete Applied Mathematics 25, 145–153 (1989) · DOI
  21. Main, M.G., Lorentz, R.J.: An O(n logn) algorithm for finding all repetitions in a string. Journal of Algorithms 5(3), 422–432 (1984) · doi:10.1016/0196-6774(84)90021-x
  22. Rodeh, M., Pratt, V.R., Even, S.: Linear algorithm for data compression via string matching. Journal of the ACM 28(1), 16–24 (1981) · doi:10.1145/322234.322237
  23. Rivals, E., Rahmann, S.: Combinatorics of periods in strings. In: van Leuween, J., Orejas, P., Spirakis, P.G. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 615–626. Springer, Heidelberg (2001) · doi:10.1007/3-540-48224-5_51
  24. Storer, J.A.: Data Compression: Methods and Theory. Computer Science Press, Rockville (1988)

Cited by

See all 2

Metadata

Authors
Duval, J.-P., Kolpakov, R., Kucherov, G., Lecroq, T., & Lefebvre, A.
Venue
Lecture Notes in Computer Science
Publisher
Springer Berlin Heidelberg
Published
2003
Pages
388-397
ISSN
  • 0302-9743
  • 1611-3349
DOI
10.1007/978-3-540-45138-9_33
Cited by
2
References
0

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Linear-Time Computation of Local Periods. https://app.cochat.ai/papers/10.1007/978-3-540-45138-9_33
The paper
Duval, J.-P., Kolpakov, R., Kucherov, G., Lecroq, T., & Lefebvre, A. (2003). Linear-Time Computation of Local Periods. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-540-45138-9_33

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.