Parameterized string matching and its application to pattern discovery

参数化字符串匹配及其在模式发现中的应用

• 批准号: 21700019
• 负责人: INENAGA Shunsuke
• 金额: $ 2.33万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21700019/
• 关键词: アルゴリズム理論; 文字列処理; データ構造; パタン発見; アルゴリズム; 文字列照合

Parameterized string matching algorithms can be used to solve several important problems on natural language text searching and biological sequence pattern discovery. We proposed efficient algorithms to solve the parameterized string matching problem, and we revealed new properties of data structures for parameterized string matching. Also, we showed a close relationship between parameterized string matching and palindrome matching, and proposed efficient algorithms for palindrome matching.

参数化的字符串匹配算法可以用来解决自然语言文本搜索和生物序列模式发现中的一些重要问题。我们提出了有效的算法来解决参数化字符串匹配问题，我们揭示了新的参数化字符串匹配的数据结构的性质。此外，我们还指出了参数化字符串匹配和回文匹配之间的密切关系，并提出了有效的回文匹配算法。

项目成果

Verifying a Parameterized Border Array in O(n1.5) Time

• DOI: 10.1007/978-3-642-13509-5_22
• 发表时间: 2010-06
• 作者: I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda

回文照合問題

回文匹配问题

• 发表时间: 2011
• 作者: 井智弘;稲永俊介;竹田正幸
• 通讯作者: 竹田正幸

Counting Parameterized Border Arrays for a Binary Alphabet.

计算二进制字母表的参数化边界数组。

• 发表时间: 2009
• 期刊: Proc. 3rd Int. Conf. on Language and Automata Theory and Applications (LATA2009) LNCS5457
• 作者: T. I;S. Inenaga;H. Bannai;M. Takeda
• 通讯作者: M. Takeda

Lightweight Parameterized Suffix Array Construction.

轻量级参数化后缀数组构造。

• 发表时间: 2009
• 期刊: Proc. 20th International Workshop on Combinatorial Algorithms(IWOCA'09),
• 作者: Tomohiro I;et.al.
• 通讯作者: et.al.

An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs Chicago Journal of Theoretical Computer Science

一种测试平衡直线程序压缩字符串无平方性的有效算法 芝加哥理论计算机科学杂志

• 发表时间: 2010
• 期刊: Special Issue : CATS 2009
• 作者: Wataru Matsubara;Shunsuke Inenaga;Ayumi Shinohara
• 通讯作者: Ayumi Shinohara