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:  sage8.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 )
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
 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
 Cc tmonteil added
comment:3 Changed 2 years ago by
 Branch set to u/nadialafreniere/improving_complexity_of_lps_and_is_symmetric_for_finite_words
comment:4 Changed 2 years ago by
 Commit set to 67f1107a726de6e4b3085e408e4940da7f74e937
 Keywords days86 added
 Milestone changed from sage6.9 to sage8.0
 Status changed from new to needs_review
comment:5 Changed 2 years ago by
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
 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
 Commit changed from 67f1107a726de6e4b3085e408e4940da7f74e937 to 73ac4e68f38d24a791209f20304c2958866d2268
If you agree with the modification, then it is a positive review.
New commits:
7759c22  Merge 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

73ac4e6  Trac 19155: Implementing Vincent Delecroix suggestion.

comment:8 Changed 20 months ago by
 Reviewers set to Mélodie Lapointe
comment:9 Changed 20 months ago by
 Status changed from needs_review to positive_review
Great! Thank you Mélodie and Vincent.
comment:10 Changed 20 months ago by
 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
New commits:
Improved lps and is_symmetric