Counting and Verifying Maximal Palindromes
スポンサーリンク
概要
- 論文の詳細を見る
A palindrome is a symmetric string that reads the same forward and backward. Let Pals(w) denote the set of maximal palindromes of a string w in which each palindrome is represented by a pair(c, r), where c is the center and r is the radius of the palindrome. We say that two strings w and z are pal-distinct if Pals(w)≠Pals(z). Firstly, we describe the number of pal-distinct strings, and show that we can enumerate all pal-distinct strings in time linear in the output size, for alphabets of size at most 3. These results follow from a close relationship between maximal palindromes and parameterized matching. Secondly, we present a linear time algorithm which finds a string w such that Pals(w) is identical to a given set of maximal palindromes.
- 2010-09-22
著者
-
TAKEDA Masayuki
Department of Urology, Niigata University School of Medicine
-
I Tomohiro
Department of Informatics, Kyushu University
-
INENAGA Shunsuke
Graduate School of Information Science and Electrical Engineering, Kyushu University
-
BANNAI Hideo
Department of Informatics, Kyushu University
-
Inenaga Shunsuke
Graduate School Of Information Science And Electrical Engineering Kyushu University
-
Bannai Hideo
Department Of Informatics Kyushu University
-
Takeda Masayuki
Department Of Urology Niigata University School Of Medicine
-
Takeda Masayuki
Department Of Informatics Kyushu University
-
Takeda Masayuki
Department Of Biochemistry And Engineering Faculty Of Engineering Tohoku University
関連論文
- Speeding Up String Pattern Matching by Text Compression: The Dawn of a New Era (特集 〔情報処理学会〕創立40周年記念論文)
- Epidermoid cyst of the penis: A case report and review of the literature
- Retroperitoneoscopy-assisted renal biopsy for pediatric patients : Comparison withretroperitoneoscopic renal biopsy
- Serum ICAM-1 in Renal Cell Cancer Patients : Possible Significance for Presence of Metastatic Disease
- Laparoscopy-Assisted Two-Stage Fowler-Stephens Orchiopexy for Intra-abdominal Nonpalpable Testis
- Counting and Verifying Maximal Palindromes
- Clinical guidelines for overactive bladder
- Modeling Costs of Access Control with Various Key Management Systems
- Validity of the Ultrasonic Aspirator and Argon Beam Coagulator in Laparoscopic Adrenalectomy for Cushing's Syndrome
- Endoscopic Parathyroidectomy for Ectopic Primary Hyperparathyroidism A Minimally Invasive Procedure for Urolithiasis Patient
- A Case of Asymptomatic Submucosal-Type Leiomyoma of the Urinary Bladder Correctly Diagnosed with Magnetic Resonance Imaging (MRI) and Successfully Treated by Transurethral Resection
- Absence of RET Proto-Oncogene Mutations in a Father and Son with Pheochromocytoma and Pancreatic Islet Cell Tumor
- Pure laparoscopic partial nephrectomy for primary renal carcinoid
- Decreased expression of G protein-coupled receptor kinases in the detrusor smooth muscle of human urinary bladder with outlet obstruction
- Modified endoscopic live donor nephrectomy : Retroperitoneoscopy followed by hand-assistance
- Clinical guidelines for nocturia
- Treatment of Multiple Intracranial Aneurysms in the Anterior Circulation : Case Report
- Characterization of the Mouse α1D-Adrenergic Receptor Gene
- Laparoscopic Renal Biopsy via the Retroperitoneal Approach : A Case Report
- The Forefront for Novel Therapeutic Agents Based on the Pathophysiology of Lower Urinary Tract Dysfunction: Pathophysiology of Voiding Dysfunction and Pharmacological Therapy
- Simultaneous management for retrocaval ureter and ipsilateral renal stone using retroperitoneoscopic approach: report of a case
- Roles of mechanosensitive ion channels in bladder sensory transduction and overactive bladder
- The use of absorbable clips for renal parenchymal suturing makes warm ischemia time short during laparoscopic partial nephrectomy in a porcine model
- Real-time quantitative analysis for human telomerase reverse transcriptase mRNA and human telomerase RNA component mRNA expressions as markers for clinicopathologic parameters in urinary bladder cancer
- Markov String Grammar
- Current and future directions in diagnostic markers in interstitial cystitis
- 183. About So-Called"Whiplash Injury"in Neurosurgical Field
- Counting and Verifying Maximal Palindromes
- 1P096 Long time folding simulations of a three-stranded antiparallel β-sheet peptide and a ββα-folded peptide(3. Protein folding and misfolding (I),Poster Session,Abstract,Meeting Program of EABS & BSJ 2006)
- Endovascular treatment of ureteroarterial fistulas with stent-grafts
- α-Methoxy-α-trifluoromethylpropionic Acid (MTPr). A New Chiral Derivatizing Reagent for GC Separation of Enantiomeric Amino Acids
- On Defining Denotational Semantics for Attribute Grammars
- Verification of an Environment Management based on Operational Semantics for Static Scope Rules
- The Forefront for Novel Therapeutic Agents Based on the Pathophysiology of Lower Urinary Tract Dysfunction : Pathophysiology of Voiding Dysfunction and Pharmacological Therapy
- Adaptive Online Prediction Using Weighted Windows
- Efficient XPath Tree Pattern Matching Algorithms over XML Data Stream
- Towards Modeling Stored-value Electronic Money Systems
- Determination of the Absolute Configuration and Enantiomeric Purity of Allylic and Acetylenic Alcohols.
- Use of axially chiral 2'-methoxy-1,1'-binaphthyl-2-carboxylic acid as chiral derivatizing agent for discrimination of enantiomeric alcohols and amines by 1H NMR.
- Muscarinic Receptor Binding of the Novel Radioligand, [3H]Imidafenacin in the Human Bladder and Parotid Gland
- Towards Modeling Stored-value Electronic Money Systems
- Metastatic Uveal Tumor Secondary to Testicular Choriocarcinoma
- Lower urinary tract symptoms in patients with Niigata Minamata disease : A case-control study 50 years after methyl mercury pollution