Please refer to the palindromic pangram problem on this page. AnalysisLet \(A_{p}\) represent a word and let \(A_{pr}\) represent its reverse. Let \(A_{1}\), \(A_{2}\), ..., \(A_{n-1}\), \(A_{n}\) be the subsequences of \(A_{pr}\) such that all of \(A_{1}\) \(A_{2}\) ..., \(A_{n-1}\) are valid words while \(A_{n}\) could be a valid word, but must be a palindrome. Then we can say that the following is a pangram for word \(A_{p}\): $$Pangram_{A_{p}} \leftarrow \sum_{i = 1}^{i = n-1} A + A_{p}$$ Let us verify if this holds true with the following two examples cited in the problem statement: $$Pangram_{daffodil} \leftarrow lid + off + a + daffodil$$ where $A_{n}$ = 'd' which is a palindrome, but not a valid word! and, $$Pangram_{ayatollahs} \leftarrow shallot + ayatollahs$$ where \(A_{n}\) = 'aya' which is a palindraome, but not a valid word! It can be easily observed here that \(A_{1}\), \(A_{2}\), ...,\(A_{n}\) are all prefixes of \(A_{pr}\). Or we can think of them as substring q of string \(A_{pr}\). We also know then that a suffix tree is a good data structure to do string matching! Algorithm
0 Comments
|
MeI am a 3D graphics software engineer. Archives
December 2011
Categories
All
|