Opened 4 years ago

Closed 20 months ago

#19155 closed defect (fixed)

Improving complexity of lps and is_symmetric for finite words

Reported by: nadialafreniere Owned by:
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords: palindromes, finite words, days 69, days86
Cc: sschanck, mlapointe, tmonteil Merged in:
Authors: Nadia Lafrenière Reviewers: Mélodie Lapointe
Report Upstream: N/A Work issues:
Branch: 73ac4e6 (Commits) Commit: 73ac4e68f38d24a791209f20304c2958866d2268
Dependencies: Stopgaps:

Description (last modified by nadialafreniere)

The purpose of this patch is to improve the complexity of is_symmetric function for words from quadratic to linear. To do this, we modify the lps (longest palindrome suffix) function to make it linear (using the last value of lps_lengths), and use a property of the longest palindrome suffix of a square.

Apart of the interest for the function in itself, the goal is to make an is_christoffel function that computes the answer in linear time (see ticket #19159).

Change History (10)

comment:1 Changed 4 years ago by nadialafreniere

  • Authors set to Nadia Lafrenière
  • Cc sschanck mlapointe added
  • Component changed from PLEASE CHANGE to combinatorics
  • Description modified (diff)
  • Keywords palindromes finite words days 69 added
  • Type changed from PLEASE CHANGE to defect

comment:2 Changed 2 years ago by tmonteil

  • Cc tmonteil added

comment:3 Changed 2 years ago by nadialafreniere

  • Branch set to u/nadialafreniere/improving_complexity_of_lps_and_is_symmetric_for_finite_words

comment:4 Changed 2 years ago by nadialafreniere

  • Commit set to 67f1107a726de6e4b3085e408e4940da7f74e937
  • Keywords days86 added
  • Milestone changed from sage-6.9 to sage-8.0
  • Status changed from new to needs_review

New commits:

67f1107Improved lps and is_symmetric

comment:5 Changed 2 years ago by vdelecroix

A small remark: the following

if l == 0:
    return self[:0]
else:
    return self[-l:]

is equivalent to this one line

return self[len(self)-l:]

comment:6 Changed 20 months ago by mlapointe

  • Branch changed from u/nadialafreniere/improving_complexity_of_lps_and_is_symmetric_for_finite_words to u/mlapointe/improving_complexity_of_lps_and_is_symmetric_for_finite_words

comment:7 Changed 20 months ago by mlapointe

  • Commit changed from 67f1107a726de6e4b3085e408e4940da7f74e937 to 73ac4e68f38d24a791209f20304c2958866d2268

If you agree with the modification, then it is a positive review.


New commits:

7759c22Merge branch 'u/nadialafreniere/improving_complexity_of_lps_and_is_symmetric_for_finite_words' of git://trac.sagemath.org/sage into t/19155/improving_complexity_of_lps_and_is_symmetric_for_finite_words
73ac4e6Trac 19155: Implementing Vincent Delecroix suggestion.

comment:8 Changed 20 months ago by mlapointe

  • Reviewers set to Mélodie Lapointe

comment:9 Changed 20 months ago by nadialafreniere

  • Status changed from needs_review to positive_review

Great! Thank you Mélodie and Vincent.

comment:10 Changed 20 months ago by vbraun

  • Branch changed from u/mlapointe/improving_complexity_of_lps_and_is_symmetric_for_finite_words to 73ac4e68f38d24a791209f20304c2958866d2268
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.