| 稲永 俊介（いねなが しゆんすけ） | データ更新日：2023.11.27 |
教授 ／
システム情報科学研究院
情報学部門
数理情報
| 1. | Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Computing SEQ-IC-LCS of non-linear texts, PSC 2023, 2023.08. |
| 2. | Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga, On Sensitivity of Compact Directed Acyclic Word Graphs, WORDS 2023, 168-180, LNCS 13899, 2023.06. |
| 3. | Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, Cristian Urbina, Bit Catastrophes for the Burrows-Wheeler Transform, DLT 2023, 10.1007/978-3-031-33264-7_8, LNCS 13911, 86-99, 2023.06. |
| 4. | Yoshifumi Sakai, Shunsuke Inenaga, A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length, Algorithmica, 10.1007/s00453-022-00968-2, 84, 9, 2581-2596, 2022.05, Abstract The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of length n such that the dissimilarity between any elements is an integer between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is $$O(c n^2)$$, which can be translated to $$O(n^2)$$ for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.. |
| 5. | Tooru Akagi, Mitsuru Funakoshi, Shunsuke Inenaga, Sensitivity of string compressors and repetitiveness measures., Inf. Comput., 10.1016/j.ic.2022.104999, 291, 104999-104999, 2023.03. |
| 6. | Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai, Space-Efficient STR-IC-LCS Computation, Proc. 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), 2023.01. |
| 7. | Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda, Parameterized DAWGs: Efficient constructions and bidirectional pattern searches, Theoretical Computer Science, 2022.10. |
| 8. | Takuya Mieno, Mitsuru Funakoshi and Shunsuke Inenaga, Computing palindromes on a trie in linear time, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 2022.12. |
| 9. | Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Proc. 29th International Symposium on String Processing and Information Retrieval (SPIRE 2022), 2022.10. |
| 10. | Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga, Minimal Absent Words on Run-Length Encoded Strings, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 11. | Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama, RePair Grammars are the Smallest Grammars for Fibonacci Words, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 12. | Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura, Cartesian Tree Subsequence Matching, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 13. | Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, and Shunsuke Inenaga, Position Heaps for Cartesian-tree Matching on Strings and Tries, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 14. | Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, On the approximation ratio of LZ-End to LZ77, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 15. | Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Common Rollercoasters, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 16. | Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Grammar Index By Induced Suffix Sorting, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 17. | Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, Counting Lyndon Subsequences, Proc. Prague Stringology Conference 2021 (PSC 2021), 2021.08. |
| 18. | Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Combinatorics of minimal absent words for a sliding window, Theoretical Computer Science, 2022.06. |
| 19. | Yoshifumi Sakai and Shunsuke Inenaga, A faster reduction of the dynamic time warping distance to the longest increasing subsequence length, Algorithmica, 2022.05. |
| 20. | Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Factorizing Strings into Repetitions, Theory of Computing Systems, 2022.04. |
| 21. | Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Palindromic trees for a sliding window and its applications, Information Processing Letters, 2022.01. |
| 22. | Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficiently computing runs on a trie, Theoretical Computer Science, 2021.10. |
| 23. | Takuya Mieno, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Minimal Unique Substrings for a Sliding Window, Algorithmica, 2021.08. |
| 24. | Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compressed Communication Complexity of Hamming Distance, Algorithms, 2021.04. |
| 25. | Hideo Bannai, Shunsuke Inenaga, and Neerja Mhaskar, Longest previous overlapping factor array, Information Processing Letters, 2021.06. |
| 26. | Shunsuke Inenaga, Towards a complete perspective on labeled tree indexing: new size bounds, efficient constructions, and beyond, Journal of Information Processing, 2021.01. |
| 27. | Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jeż, and Markus Lohrey, The Smallest Grammar Problem Revisited, IEEE Transactions on Information Theory, 2021.01. |
| 28. | Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Space-efficient algorithms for computing minimal/shortest unique substrings, Theoretical Computer Science, 2020.12. |
| 29. | Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Grammar-compressed Self-index with Lyndon Words, IPSJ Transactions on Mathematical Modeling and its Applications, 2020.08. |
| 30. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Parameterized Suffix Tray, Proc. 12th International Conference on Algorithms and Complexity (CIAC 2021), 2021.05. |
| 31. | Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello, Novel Results on the Number of Runs of the Burrows-Wheeler-Transform, Proc. 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), 2021.01. |
| 32. | Shunsuke Inenaga, Suffix Trees, DAWGs, and CDAWGs for Forward and Backward Tries, Proc. 14th Latin American Theoretical Informatics Symposium (LATIN 2020), 2021.01. |
| 33. | Yoshifumi Sakai and Shunsuke Inenaga, A reduction of the dynamic time warping distance to the longest increasing subsequence length, 31st International Symposium on Algorithms and Computation (ISAAC 2020), 2020.12. |
| 34. | Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, On repetitiveness measures of Thue-Morse words, 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), 2020.10. |
| 35. | Takafumi Inoue, Shunsuke Inenaga, and Hideo Bannai, Longest Square Subsequence Problem Revisited, 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), 2020.10. |
| 36. | Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Towards Efficient Interactive Computation of Dynamic Time Warping Distance, 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), 2020.10. |
| 37. | Shunsuke Inenaga, Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings, Proc. Prague Stringology Conference 2020 (PSC 2020), 2020.08. |
| 38. | Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, DAWGs for Parameterized Matching Online Construction and Related Indexing Structures, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, 10.4230/LIPIcs.CPM.2020.26, 2020.06, [URL], Two strings x and y over of equal length are said to parameterized match (p-match) if there is a renaming bijection f : That is identity on and transforms x to y (or vice versa). The p-matching problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose parameterized suffix automata (p-suffix automata) and parameterized directed acyclic word graphs (PDAWGs) which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have(n2) nodes and edges but PDAWGs have only O(n) nodes and edges, where n is the length of an input string. We also give O(n log( + ))-time O(n)-space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the parameterized suffix tree for the reversed string can also be built in the same time and space, in a right-to-left online manner. 2012 ACM Subject Classification Theory of computation ! Pattern matching.. |
| 39. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Ayumi Shinohara, Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, 10.4230/LIPIcs.CPM.2020.12, 2020.06, [URL], The equidistant subsequence pattern matching problem is considered. Given a pattern string P and a text string T, we say that P is an equidistant subsequence of T if P is a subsequence of the text such that consecutive symbols of P in the occurrence are equally spaced. We can consider the problem of equidistant subsequences as generalizations of (sub-)cadences. We give bit-parallel algorithms that yield o(n2) time algorithms for finding k-(sub-)cadences and equidistant subsequences. Furthermore, O(n log2 n) and O(n log n) time algorithms, respectively for equidistant and Abelian equidistant matching for the case P = 3, are shown. The algorithms make use of a technique that was recently introduced which can efficiently compute convolutions with linear constraints. 2012 ACM Subject Classification Mathematics of computing ! Combinatorial algorithms.. |
| 40. | Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara, Efficient computation of longest single-arm-gapped palindromes in a string, Theoretical Computer Science, 10.1016/j.tcs.2019.10.025, 812, 160-173, 2020.04, [URL], In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either wgucuRwR or wucuRgwR, where w and u are non-empty strings, wR and uR are respectively the reversed strings of w and u, g is a string called a gap, and c is either a single character or the empty string. Here we call wu and uRwR the arm of the SAGP, and |uv| the length of the arm. We classify SAGPs into two groups: those which have ucuR as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute type-1 SAGPs with longest arms occurring in a given string, based on suffix arrays. Then, we propose a linear-time algorithm to compute all type-1 SAGPs with longest arms, based on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms in linear time. We also perform some preliminary experiments to show practical performances of the proposed methods.. |
| 41. | Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida, Practical Grammar Compression Based on Maximal Repeats, Algorithms, https://doi.org/10.3390/a13040103, 13, 4, 103, 2020.04. |
| 42. | Takaaki Nishimoto, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Discrete Applied Mathematics, 10.1016/j.dam.2019.01.014, 274, 15, 116-129, 2020.03, [URL]. |
| 43. | Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic Trie Tailored for Fast Prefix Searches, Data Compression Conference 2020 (DCC 2020), 2020.03. |
| 44. | Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), 2020.01. |
| 45. | Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster STR-EC-LCS Computation, 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), 2020.01. |
| 46. | Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings, Theory of Computing Systems, 10.1007/s00224-020-09980-x, 2020.01, [URL], For a string S, a palindromic substring S[i.j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if S[i.j] occurs exactly once in S, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter than S[i.j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLES of size m in O(m) space and O(mlogσRLES+mlogm/loglogm) time so that all SUPSs for any subsequent query interval can be answered in O(logm/loglogm+α) time, where α is the number of outputs, and σRLES is the number of distinct runs of RLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in O(loglogm/logloglogm+α) time and can be built in O(mlogσRLES+mlogm/loglogm) time, and the second one answers queries in O(log log m+ α) time and can be built in O(mlogσRLES) time. Both of these data structures require O(m) space.. |
| 47. | Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Space-efficient algorithms for computing minimal/shortest unique substrings, Theoretical Computer Science, 10.1016/j.tcs.2020.09.017, 2020.12, [URL], Given a string T of length n, a substring u=T[i..j] of T is called a shortest unique substring (SUS) for an interval [s,t] if (a) u occurs exactly once in T, (b) u contains the interval [s,t] (i.e. i≤s≤t≤j), and (c) every substring v of T with |v|23+1)n⌉+o(n) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.. |
| 48. | Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An Improved Data Structure for Left-Right Maximal Generic Words Problem, 30th International Symposium on Algorithms and Computation, ISAAC 2019, 10.4230/LIPIcs.ISAAC.2019.40, 40:1-40:12, 2019.12, [URL]. |
| 49. | Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, and Ayumi Shinohara, Efficient Dynamic Dictionary Matching with DAWGs and AC-automata, Theoretical Computer Science, 2019.11. |
| 50. | Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of the smallest alphabet for Lyndon trees, Theoretical Computer Science, 10.1016/j.tcs.2018.06.044, 792, 131-143, 2019.11. |
| 51. | Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compact Data Structures for Shortest Unique Substring Queries, 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), 2019.10. |
| 52. | Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, and Tomasz Kociumaka, On Longest Common Property Preserved Substring Queries, 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), 2019.10. |
| 53. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets, 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), 2019.10. |
| 54. | Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Dany Breslauer, and Diptarama Hendrian, Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts, Algorithmica, 2019.10. |
| 55. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Maximal Palindromes and Distinct Palindromes in a Trie, Prague Stringology Conference 2019 (PSC 2019), 2019.08. |
| 56. | Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, Tomohiro I, Shunsuke Inenaga and Shiho Sugimoto, k-Abelian pattern matching: Revisited, corrected, and extended, Prague Stringology Conference 2019 (PSC 2019), 2019.08. |
| 57. | Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings, The 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), 2019.07. |
| 58. | Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing runs on a trie, Proc. the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 2019.06. |
| 59. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster queries for longest substring palindrome after block edit, Proc. the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 2019.06. |
| 60. | Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations, Proc. the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 2019.06. |
| 61. | Diptarama Hendrian, Takuya Takagi, and Shunsuke Inenaga, Online Algorithms for Constructing Linear-size Suffix Trie, Proc. the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 2019.06. |
| 62. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Parameterized Position Heap of a Trie, 11th International Conference on Algorithms and Complexity (CIAC 2019), 2019.05. |
| 63. | Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Takuya Kida, MR-RePair: Grammar Compression based on Maximal Repeats, Data Compression Conference 2019 (DCC 2019), 2019.03. |
| 64. | Keisuke Goto, Tomohiro I, Hideo Bannai and Shunsuke Inenaga, Block Palindromes: A New Generalization of Palindromes, 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), 2018.10. |
| 65. | Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays, 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), 2018.10. |
| 66. | Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Algorithms and combinatorial properties on shortest unique palindromic substrings, Journal of Discrete Algorithms, 10.1016/j.jda.2018.11.009, 52-53, 122-132, 2018.09, [URL], A palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s,t], and every palindromic substring of S which contains interval [s,t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUPSs for interval [s,t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O(n) time and space so that all SUPSs for any subsequent query interval can be answered in O(α+1) time, where α is the number of outputs. We also discuss the number of SUPSs in a string.. |
| 67. | Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, Prague Stringology Conference 2018 (PSC 2018), 2018.08. |
| 68. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Right-to-left Online Construction of Parameterized Position Heaps, Prague Stringology Conference 2018 (PSC 2018), 2018.08. |
| 69. | Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Faster Online Elastic Degenerate String Matching, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07. |
| 70. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest substring palindrome after edit, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07. |
| 71. | Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, and Masayuki Takeda, Computing longest common square subsequences, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07. |
| 72. | Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Lyndon Substring After Edit, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07. |
| 73. | Isamu Furuya, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Lyndon Factorization of Grammar Compressed Texts Revisited, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07. |
| 74. | Heikki Hyyrö, Shunsuke Inenaga, Dynamic RLE-Compressed Edit Distance Tables under General Weighted Cost Functions, International Journal of Foundations of Computer Science, 10.1142/S0129054118410083, 29, 4, 623-645, 2018.06, [URL], Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302-312, 2004] proposed a method (KP) based on a "dynamic edit distance table" that allows one to efficiently maintain unit cost edit distance information between two strings A of length m and B of length n when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, O(m + n), to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in O(c(m + n)) time per single edit, where c is the maximum weight of the cost function. The work noted that the Θ(mn) space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing A and B. Let M and N be the lengths of RLE compressed versions of A and B, respectively. We propose how to store the dynamic edit distance table using Θ(mN + Mn) space while maintaining the same time complexity as the previous methods for uncompressed strings.. |
| 75. | Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Karkkainen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, International Journal of Foundations of Computer Science, 10.1142/S0129054118400014, 29, 2, 143-163, 2018.02. |
| 76. | Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, Journal of Foundations of Computer Science, http://dx.doi.org/10.1142/S0129054118400014, 143-163, 29(2):143-163, 2018.02. |
| 77. | Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piakowski, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, International Journal of Foundations of Computer Science, 10.1142/S0129054118400014, 29, 2, 143-163, 2018.02, We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.. |
| 78. | Shunsuke Inenaga and Heikki Hyyro, A hardness result and new algorithm for the longest common palindromic subsequence problem, Information Processing Letters, 10.1016/j.ipl.2017.08.006, 129, 11-15, 2018.01. |
| 79. | Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Koppl, and Florin Manea, Inferring strings from Lyndon factorization, Theory of Computing Systems, 10.1007/s00224-017-9794-5, 62, 1, 162-191, 2018.01. |
| 80. | Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, Ayumi Shinohara, Efficient dynamic dictionary matching with DAWGs and AC-automata, Theoretical Computer Science, 10.1016/j.tcs.2018.04.016, 2018.01, [URL], The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho–Corasick-automaton (AC-automaton) which is built on D is a fundamental data structure which enables us to solve the dictionary matching problem in O(dlogσ) preprocessing time and O(nlogσ+occ) matching time, where d is the total length of the patterns in the dictionary D, n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from the dictionary D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms that can solve both problems with some modifications. For a pattern of length m, our first algorithm supports insertions in O(mlogσ+logd/loglogd) time and pattern matching in O(nlogσ+occ) for the semi-dynamic setting. This algorithm also supports both insertions and deletions in O(σm+logd/loglogd) time and pattern matching in O(n(logd/loglogd+logσ)+occ(logd/loglogd)) time for the dynamic dictionary matching problem by some modifications. This algorithm is based on the directed acyclic word graph (DAWG) of Blumer et al. (JACM 1987). Our second algorithm, which is based on the AC-automaton, supports insertions in O(mlogσ+uf+uo) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+uf+uo) time for the dynamic setting, where uf and uo respectively denote the numbers of states in which the failure function and the output function need to be updated. This algorithm performs pattern matching in O(nlogσ+occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods over constant-size alphabets, since any algorithm which explicitly maintains the AC-automaton requires Ω(m+uf+uo) update time.. |
| 81. | Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of the smallest alphabet for Lyndon trees, Theoretical Computer Science, 10.1016/j.tcs.2018.06.044, 2018.01, [URL], We consider the problem of reverse-engineering the Lyndon tree, i.e., given a full binary ordered tree T with n leaves as input, we are to compute a string w of length n of which Lyndon tree is isomorphic to the input tree T. Hereby we call such a string a solution string. Although the problem is easily solvable in linear time for binary alphabets and unbounded-size alphabets, it is not known how to efficiently find the smallest alphabet size for a solution string. In this paper, we show several new observations concerning this problem. Namely, we show that: 1) For any positive integer n, there exists a full binary ordered tree T with n leaves, s.t. the smallest alphabet size of a solution string for T is ⌊[Formula presented]⌋+1. 2) For any full binary ordered tree T with n leaves, there exists a solution string w over an alphabet of size at most ⌊[Formula presented]⌋+1. 3) For any full binary ordered tree T, there exists a solution string w over an alphabet of size at most h+1, where h is the height of T. 4) For any complete binary ordered tree T with 2k leaves, there exists a solution string w over an alphabet of size at most 4.. |
| 82. | Shunsuke Inenaga, Heikki Hyyro, A hardness result and new algorithm for the longest common palindromic subsequence problem, INFORMATION PROCESSING LETTERS, 10.1016/j.ipl.2017.08.006, 129, 11-15, 2018.01, The 2-LCPS problem, first introduced by Chowdhury et al. (2014) [17], asks one to compute (the length of) a longest common palindromic subsequence between two given strings A and B. We show that the 2-LCPS problem is at least as hard as the well-studied longest common subsequence problem for four strings. Then, we present a new algorithm which solves the 2-LCPS problem in O (sigma M-2 + n) time, where n denotes the length of A and B, M denotes the number of matching positions between A and B, and a denotes the number of distinct characters occurring in both A and B. Our new algorithm is faster than Chowdhury et al.'s sparse algorithm when sigma = o(log(2) n log log n). (C) 2017 Elsevier B.V. All rights reserved.. |
| 83. | Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets., Theory Comput. Syst., 10.1007/s00224-017-9794-5, 62, 1, 162-191, 2018.01. |
| 84. | Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Almost linear time computation of maximal repetitions in run length encoded strings, 28th International Symposium on Algorithms and Computation, ISAAC 2017, 10.4230/LIPIcs.ISAAC.2017.33, 92, 2017.12, [URL], We consider the problem of computing all maximal repetitions contained in a string that is given in run-length encoding. Given a run-length encoding of a string, we show that the maximum number of maximal repetitions contained in the string is at most m+k-1, where m is the size of the run-length encoding, and k is the number of run-length factors whose exponent is at least 2. We also show an algorithm for computing all maximal repetitions in O(m α (m)) time and O(m) space, where α denotes the inverse Ackermann function.. |
| 85. | Kazuyuki Narisawa, Hideharu Hiratsuka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, ALGORITHMICA, 10.1007/s00453-016-0178-z, 79, 2, 291-318, 2017.10, This paper considers enumeration of substring equivalence classes introduced by Blumer et al. (J ACM 34(3):578-595, 1987). These equivalence classes were originally proposed to define a text indexing structure called compact directed acyclic word graphs (CDAWGs). These equivalence classes are also useful for text analysis, since they group together redundant substrings with essentially identical occurrences. In this paper, we present how to enumerate these equivalence classes using only suffix arrays and two auxiliary arrays (rank arrays and lcp arrays), in O(n) time for a given string of length n over the integer alphabet. The proposed method overcomes all the existing algorithms which require time O(n log sigma), where sigma is the alphabet size. Our experimental results show that the proposed method is also practically faster and more memory efficient than the existing ones. Furthermore, we propose an O(n)-time algorithm which constructs the CDAWG of an input string over the integer alphabet. This algorithm is based on the above-mentioned algorithm to enumerate equivalence classes. Our experiments show that the proposed method runs faster than the existing algorithm on large alphabets.. |
| 86. | Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon Puglisi, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_5, LNCS 10508, 51-67, 2017.09. |
| 87. | Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga and Hiroki Arimura, Linear-size CDAWG: new repetition-aware indexing and grammar compression, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_26, LNCS 10508, 304-316, 2017.09. |
| 88. | Tenma Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Order preserving pattern matching on trees and DAGs, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_23, LNCS 10508, 271-277, 2017.09. |
| 89. | Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta, The "Runs" Theorem, SIAM Journal of Computing, 10.1137/15M1011032, 46, 5, 1501-1514, 2017.09. |
| 90. | Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, and Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 10.1587/transfun.E100.A.1785, E100-A, 9, 1785-1793, 2017.09. |
| 91. | Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura, Packed compact tries: A fast and efficient data structure for online string processing, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 10.1587/transfun.E100.A.1785, E100A, 9, 1785-1793, 2017.09, We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log + O(k log n) bits of space and supports fast pattern matching queries and updates, where is the alphabet size. Assume that = log n letters are packed in a single machine word on the standard word RAM model, and let f (k n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1 n] in O(k log n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in O( m f (k n)) worst-case time and in O( m + f (k n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.. |
| 92. | Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, On Reverse Engineering the Lyndon Tree, Prague Stringology Conference 2017 (PSC 2017), 108-117, 2017.08, [URL]. |
| 93. | Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Small-space LCE data structure with constant-time queries, Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 10.4230/LIPIcs.dMFCS.2017.10, 10:1-10:15, 2017.08. |
| 94. | Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Koppl, and Florin Manea, Inferring strings from Lyndon factorization, Theory of Computing Systems, 10.1007/s00224-017-9794-5, 62, 1, 162-191, 2017.08. |
| 95. | Yuto Nakashima, Takashi Okabe, Tomohiro, I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2017.05.038, 689, 147-156, 2017.08, The Lyndon factorization of a string w is a unique factorization l(1)(p1),..., l(m)(pm) of w such that l(1),..., l(m) is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S = ((s(1), p(1)) (s(m), p(m))) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, i.e., the Lyndon factorization of w is in a form of l(1)(p1),..., l(m)(pm) with vertical bar l(i)vertical bar = s(i) for all 1 |
| 96. | Hideo Bannai, Shunsuke Inenaga, Dominik Köppl, Computing All Distinct Squares in Linear Time for Integer Alphabets, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 97. | Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-IC-LCS computation via RLE, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 98. | Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tight bounds on the maximum number of shortest unique substrings, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 99. | Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Palindromic Substring Queries in Optimal Time, The 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07. |
| 100. | Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian string regularities based on RLE, The 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07. |
| 101. | Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Longest Common Subsequence in at Least k Length Order-isomorphic Substrings, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 10.1007/978-3-319-51963-0_28, LNCS 10139, 363-374, 2017.01. |
| 102. | Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara, Computing longest single-arm-gapped palindromes in a string, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 10.1007/978-3-319-51963-0_29, LNCS 10139, 375-386, 2017.01. |
| 103. | Tomohiro, I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2016.03.005, 656, 215-224, 2016.12, We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n that describes w, the first algorithm runs in O (n(2) + P (n, N) Q (n, N)n logn) time and O (n(2) + S(n, N)) space, where P(n, N), S(n, N), Q(n, N) are respectively the preprocessing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O (s logs) time and space. (C) 2016 Elsevier B.V. All rights reserved.. |
| 104. | Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Generalized pattern matching and periodicity under substring consistent equivalence relations, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2016.02.017, 656, 225-233, 2016.12, Let approximate to be a substring consistent equivalence relation (SCER) on strings such that for any two strings x, y, x approximate to y implies that (1) vertical bar x vertical bar = vertical bar y vertical bar and (2) x[i..j] approximate to y[i..j] for all 0 |
| 105. | Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, Theoretical Computer Science, 10.1016/j.tcs.2016.03.005, 656(B), 215-224, 2016.11. |
| 106. | Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Generalized pattern matching and periodicity under substring consistent equivalence relations, Theoretical Computer Science, 10.1016/j.tcs.2016.02.017, 656(B), 215-224, 2016.11. |
| 107. | Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Shunsuke Inenaga, Costas S. Iliopoulos, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Discrete Applied Mathematics, 10.1016/j.dam.2016.04.009, 212, 23-29, 2016.10. |
| 108. | Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro, I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, Shiho Sugimoto, Closed factorization, DISCRETE APPLIED MATHEMATICS, 10.1016/j.dam.2016.04.009, 212, 23-29, 2016.10, A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we present algorithms for computing closed factors (substrings) in strings. First, we consider the problem of greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(n log n/log log n) time, where n is the length of the string. This also leads to an algorithm to compute the maximal closed factor containing (i.e. covering) each position in the string in O(n log n/log log n) time. We also present linear time algorithms to factorize a string into a sequence of shortest closed factors of length at least two, to compute the shortest closed factor of length at least two starting at each position of the string, and to compute a minimal closed factor of length at least two containing each position of the string. (C) 2016 Elsevier B.V. All rights reserved.. |
| 109. | Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding gapped palindromes online, Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 10.1007/978-3-319-44543-4_15, Lecture Notes in Computer Science 9843, 191-202, 2016.08. |
| 110. | Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 10.1007/978-3-319-44543-4_17, LNCS 9843, 213-225, 2016.08. |
| 111. | Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully dynamic data structure for LCE queries in compressed space, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.72, 72:1-72:15, 2016.08. |
| 112. | Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.69, 69:1-69:11, 2016.08. |
| 113. | Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.38, 38:1-38:14, 2016.08. |
| 114. | Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Proc. Prague Stringology Conference 2016, 153-171, 2016.08. |
| 115. | Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) time, Proc. Prague Stringology Conference 2016 (PSC 2016), 135-145, 2016.08. |
| 116. | Kazuyuki Narisawa, Hideharu Hiratsuka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Algorithmica, 10.1007/s00453-016-0178-z, 2016.08. |
| 117. | Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Factorizing a string into squares in linear time, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.27, 27:1-27:12, 2016.06. |
| 118. | Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon Puglisi, Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.1, 2016.06. |
| 119. | Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Fully-online construction of suffix trees for multiple texts, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.22, 22:1-22:13, 2016.06. |
| 120. | Yuka Tanimura, I. Tomohiro, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, Leibniz International Proceedings in Informatics, LIPIcs, 10.4230/LIPIcs.CPM.2016.1, 54, 1.1-1.10, 2016.06, Given a string S of n symbols, a longest common extension query LCE(i, j) asks for the length of the longest common prefix of the ith and jth suffixes of S. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015:65-76) described several data structures for answering LCE queries that offers a trade-off between data structure size and query time. In particular, for a parameter 1 ≤ τ ≤ n, their best deterministic solution is a data structure of size O(n/τ) which allows LCE queries to be answered in O(τ) time. However, the construction time for all deterministic versions of their data structure is quadratic in n. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of O(τ min{log τ, log n/τ}) query time using O(n/τ) space, but we significantly improve the construction time to O(nτ).. |
| 121. | Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Efficiently Finding All Maximal α-gapped Repeats, Proc. the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 10.4230/LIPIcs.STACS.2016.39, 39:1-39:14, 2016.02. |
| 122. | Paweł Gawrychowski, I. Tomohiro, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Efficiently finding all maximal α-gapped repeats, Leibniz International Proceedings in Informatics, LIPIcs, 10.4230/LIPIcs.STACS.2016.39, 47, 39:1-39:14, 2016.02, For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|u| the two occurrences of a factor u in such a repeat are called arms. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn, allowing us to construct an algorithm finding all maximal α-gapped repeats of a word on an integer alphabet of size nO(1) in O(αn) time. This result is optimal as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvuT with |uv| ≤ α|u|.. |
| 123. | Heikki Hyyro, Shunsuke Inenaga, Compacting a dynamic edit distance table by RLE compression, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), 34, 302-313, 2016.01. |
| 124. | Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, Proc. 26th International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science, 2015.12. |
| 125. | Yuto Nakashima, Tomihiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets, Information Processing Letters, 115, 9, 655-659, 2015.09. |
| 126. | Heikki Hyyro, Kazuyuki Narisawa, Shunsuke Inenaga, Dynamic Edit Distance Table under a General Weighted Cost Function, Journal of Discrete Algorithms, 34, 2-17, 2015.09. |
| 127. | Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Waleń, Efficient Algorithms for Longest Closed Factor Array, Proc. the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_10, Lecture Notes in Computer Science 9309, 95-102, 2015.09. |
| 128. | Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A faster algorithm for computing maximal α-gapped repeats in a string, Proc. the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_13, Lecture Notes in Computer Science 9309, 124-136, 2015.09. |
| 129. | Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Constructing LZ78 tries and position heaps in linear time for large alphabets, Information Processing Letters, 10.1016/j.ipl.2015.04.002, 115, 9, 655-659, 2015.09, We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marked ancestor queries on the suffix tree of the given string. We also show that the same technique can be used to construct the position heap of a set of strings in worst-case linear time, when the set of strings is given as a trie.. |
| 130. | Heikki Hyyrö, Kazuyuki Narisawa, Shunsuke Inenaga, Dynamic edit distance table under a general weighted cost function, Journal of Discrete Algorithms, 10.1016/j.jda.2015.05.007, 34, 2-17, 2015.09, We discuss the problem of edit distance computation under a dynamic setting, where one of the two compared strings may be modified by single-character edit operations and we wish to keep the edit distance information between the strings up-to-date. A previous algorithm by Kim and Park (2004) [6] solves a more limited problem where modifications can be done only at the ends of the strings (so-called decremental or incremental edits) and the edit operations have (essentially) unit costs. If the lengths of the two strings are m and n, their algorithm requires O(m+n) time per modification. We propose a simple and practical algorithm that (1) allows arbitrary non-negative costs for the edit operations and (2) allows the modifications to be done at arbitrary positions. If the latter string is modified at position < sup> j∗< /sup> , our algorithm requires O(min {rc(m+n),mn}) time, where r=min {< sup> j∗< /sup> ,n-< sup> j∗< /sup> +1} and c is the maximum edit operation cost. This equals O(m+n) in the simple decremental/incremental unit cost case. Our experiments indicate that the algorithm performs much faster than the theoretical worst-case time limit O(mn) in the general case with arbitrary edit costs and modification positions. The main practical limitation of the algorithm is its Θ(mn) memory requirement for storing the edit distance information.. |
| 131. | Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proc. the Prague Stringology Conference 2015 (PSC 2015), 5-16, 2015.08. |
| 132. | Shunsuke Inenaga, A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications, Proc. the Prague Stringology Conference 2015 (PSC 2015), 1-4, 2015.08. |
| 133. | Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, Proc. the 19th International Conference on Developments in Language Theory (DLT 2015), 10.1007/978-3-319-21500-6_6, Lecture Notes in Computer Science 9168, 85-96, 2015.07. |
| 134. | Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-19929-0_30, Lecture Notes in Computer Science 9133, 355-366, 2015.06. |
| 135. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-19929-0_19, Lecture Notes in Computer Science 9133, 219-230, 2015.06. |
| 136. | Tomihiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed automata for dictionary matching, Theoretical Computer Science, 578, 30-41, 2015.05. |
| 137. | Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, Proc. the 9th International Conference on Algorithms and Complexity (CIAC 2015), 10.1007/978-3-319-18173-8_29, Lecture Notes in Computer Science 9079, 390-402, 2015.05. |
| 138. | Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed automata for dictionary matching, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2015.01.019, 578, 30-41, 2015.05, We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing in patterns of total length N, we present an O (n(2) log N)-size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O (h + m) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O (n(3) logn log N) time and O (n(2) log N) space. In a spacial case where 7, represents only a single pattern, we present an O (n log N)-size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O (h) running time per character, and we show how to construct this representation in O (n(3) logn log N) time with O (n(2) log N) working space. (C) 2015 Elsevier B.V. All rights reserved.. |
| 139. | Tomohiro I, Kouji Shimohira, Wataru Matsubara, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting regularities on grammar-compressed strings, Information and Computation, 10.1016/j.ic.2014.09.009, 240, 74-89, 2015.02. |
| 140. | Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting regularities on grammar-compressed strings, INFORMATION AND COMPUTATION, 10.1016/j.ic.2014.09.009, 240, 74-89, 2015.02, We address the problems of detecting and counting various forms of regularities in a string represented as a straight-line program (SLP) which is essentially a context free grammar in the Chomsky normal form. Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in sin O(n(3)h) time and O(n(2)) space, where his the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n(3)h + gnh logN) time and O(n(2)) space, where g is the length of the gap. As one of the main components of the above solution, we propose a new technique called approximate doubling which seems to be a useful tool for a wide range of algorithms on SLPs. Indeed, we show that the technique can be used to compute the periods and covers of the string in O(n(2)h) time and O(nh(n + log(2)N)) time, respectively. (C) 2014 Elsevier Inc. All rights reserved.. |
| 141. | Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, Proc. ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA 2015), 10.1137/1.9781611973730.38, 562-571, 2015.01. |
| 142. | Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Shunsuke Inenaga, Costas S. Iliopoulos, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Proc. the Prague Stringology Conference 2014 (PSC 2014), 162-168, 2014.09. |
| 143. | Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian Covers and Abelian Runs, Proc. the Prague Stringology Conference 2014 (PSC 2014), 43-51, 2014.09. |
| 144. | Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, Proc. the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), 10.1007/978-3-662-44465-8_48, Lecture Notes in Computer Science 8635, 565-576, 2014.08. |
| 145. | Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, Proc. 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), 10.1007/978-3-319-07566-2_16, Lecture Notes in Computer Science 8486, 150-161, 2014.06. |
| 146. | Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, Proc. 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 10.4230/LIPIcs.STACS.2014.675, Leibniz International Proceedings in Informatics (LIPIcs) 25, 675-686, 2014.03. |
| 147. | Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, Discrete Applied Mathematics, dx.doi.org/10.1016/j.dam.2013.02.033, 163, 3, 316-325, 2014.01. |
| 148. | Kazuya Tsuruta, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, Proc. 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 10.1007/978-3-319-04298-5_44, LNCS 8327, 503-513, 2014.01. |
| 149. | Tomohiro, I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from suffix trees and links on a binary alphabet, DISCRETE APPLIED MATHEMATICS, 10.1016/j.dam.2013.02.033, 163, 316-325, 2014.01, A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. (C) 2013 Elsevier B.V. All rights reserved.. |
| 150. | Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text, Proc. the 20th Symposium on String Processing and Information Retrieval (SPIRE 2013), 10.1007/978-3-319-02432-5_21, Lecture Notes in Computer Science 8214, 174-185, 2013.10. |
| 151. | Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed Automata for Dictionary Matching, Proc. the 18th International Conference on Implementation and Application of Automata (CIAA 2013), 10.1007/978-3-642-39274-0_28, Lecture Notes in Computer Science 7982, 319-330, 2013.10. |
| 152. | Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga, Masayuki Takeda, Converting SLP to LZ78 in almost linear time, Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 10.1007/978-3-642-38905-4_6, Lecture Notes in Computer Science 7922, 38-49, 2013.10. |
| 153. | Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 10.1007/978-3-642-38905-4_16, Lecture Notes in Computer Science 7922, 153-164, 2013.10. |
| 154. | Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, Proc. the Prague Stringology Conference 2013 (PSC 2013), 107-118, 2013.08. |
| 155. | Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Sninohara, Detecting Regularities on Grammar-compressed Strings, Proc. the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 10.1007/978-3-642-40313-2_51, Lecture Notes in Computer Science 8087, 571-582, 2013.08. |
| 156. | Tomohiro I, Shunsuke Inenaga, Masayuki Takeda, Palindrome Pattern Matching, Theoretical Computer Science, dx.doi.org/10.1016/j.tcs.2012.01.047, 483, 162-170, 2013.04. |
| 157. | Tomohiro, I, Shunsuke Inenaga, Masayuki Takeda, Palindrome pattern matching, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2012.01.047, 483, 162-170, 2013.04, A palindrome is a string that reads the same forward and backward. For a string x, let Pals(x) be the set of all maximal palindromes of x, where each maximal palindrome in Pals(x) is encoded by a pair (c, r) of its center c and its radius r. Given a text t of length n and a pattern p of length m, the palindrome pattern matching problem is to compute all positions i oft such that Pals(p) = Pals(t[i : i + m - 1]). We present linear-time algorithms to solve this problem. (C) 2012 Elsevier B.V. All rights reserved.. |
| 158. | Yuya Tamakoshi, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, Proc. Data Compression Conference 2013 (DCC 2013), 2013.03. |
| 159. | Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing convolution on grammar-compressed text, Proc. Data Compression Conference 2013 (DCC 2013), 2013.03. |
| 160. | Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga, Permuted Pattern Matching on Multi-Track Strings, Proc. the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), dx.doi.org/10.1007/978-3-642-35843-2_25, Lecture Notes in Computer Science 7741, 280-291, 2013.01. |
| 161. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram mining on SLP compressed strings, Journal of Discrete Algorithms, dx.doi.org/10.1016/j.jda.2012.07.006, 18, 89-99, 2013.01. |
| 162. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram mining on SLP compressed strings, Journal of Discrete Algorithms, 10.1016/j.jda.2012.07.006, 18, 89-99, 2013.01, We present simple and efficient algorithms for calculating q-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP of size n that represents string T, we present an O(qn) time and space algorithm that computes the occurrence frequencies of all q-grams in T. Computational experiments show that our algorithm and its variation are practical for small q, actually running faster on various real string data, compared to algorithms that work on the uncompressed text. We also discuss applications in data mining and classification of string data, for which our algorithms can be useful. © 2012 Elsevier B.V.. |
| 163. | Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient LZ78 Factorization of Grammar Compressed Text, Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), dx.doi.org/10.1007/978-3-642-34109-0_10, Lecture Notes in Computer Science 7608, 86-98, 2012.10. |
| 164. | Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Position Heap of a Trie, Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), dx.doi.org/10.1007/978-3-642-34109-0_38, Lecture Notes in Computer Science 7608, 360-371, 2012.10. |
| 165. | Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Information Processing Letters, dx.doi.org/10.1016/j.ipl.2012.06.017, 122, 9, 711-714, 2012.10. |
| 166. | Hideo Bannai, Travis Gagie, Tomohiro, I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, INFORMATION PROCESSING LETTERS, 10.1016/j.ipl.2012.06.017, 112, 19, 711-714, 2012.10, We give a simple algorithm that, given a straight-line program of size n for a string S of length N, tests whether S is square-free in O(n(4) log N) time and O(n(2)) space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S. in O(c(4) log(5) N) time and O(c(2) log(2) N) space, which is faster than using the algorithm by Gasieniec, Karpinski, Plandowski, and Rytter (1996) [4]. (C) 2012 Elsevier B.V. All rights reserved.. |
| 167. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Speeding-up q-gram mining on grammar-based compressed texts, Proc. the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), dx.doi.org/10.1007/978-3-642-31265-6_18, Lecture Notes in Computer Science 7354, 220-231, 2012.07. |
| 168. | Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, dx.doi.org/10.1142/S0129054112400126, 23, 2, 261-280, 2012.02. |
| 169. | Shunsuke Inenaga, Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, dx.doi.org/10.1142/S0129054112400126, 23, 2, 261-280, 2012.02. |
| 170. | Shunsuke Inenaga, Hideo Bannai, FINDING CHARACTERISTIC SUBSTRINGS FROM COMPRESSED TEXTS, INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 10.1142/S0129054112400126, 23, 2, 261-280, 2012.02, Text mining from large scaled data is of great importance in computer science. In this paper, we consider fundamental problems on text mining from compressed strings, i.e., computing a longest repeating substring, longest non-overlapping repeating substring, most frequent substring, and most frequent non-overlapping substring from a given compressed string. Also, we tackle the following novel problem: given a compressed text and compressed pattern, compute the representative of the equivalence class of the pattern w.r.t. the text. We present algorithms that solve the above problems in time polynomial in the size of input compressed strings. The compression scheme we consider is straight line program (SLP) which has exponential compression, and therefore our algorithms are more efficient than any existing algorithms that require decompression of given SLPs.. |
| 171. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, Proc. the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), dx.doi.org/10.1007/978-3-642-27660-6_25, Lecture Notes in Computer Science 7147, 301-312, 2012.01. |
| 172. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Verifying and Enumerating Parameterized Border Arrays, Theoretical Computer Science, dx.doi.org/10.1016/j.tcs.2011.09.008, 412, 50, 6959-6981, 2011.11. |
| 173. | Tomohiro, I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Verifying and enumerating parameterized border arrays, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2011.09.008, 412, 50, 6959-6981, 2011.11, The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. This algorithm runs in O(B-2(n)) time, where B-2(n) is the number of all p-border arrays of length n for a binary parameter alphabet. The problems with a larger alphabet are much more difficult. Still, we present an O(n(1.5)) - time O(n) - space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the n-th Bell number 1/e Sigma(infinity)(k=0) k(n)/k(l), and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most n for an unbounded alphabet in O(B(n)n(2.5)) time, where B-n denotes the number of p-border arrays of length n. (C) 2011 Elsevier B.V. All rights reserved.. |
| 174. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, Proc. the 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), LNCS 7024, 278-289, 2011.10. |
| 175. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, Proc. The Prague Stringology Conference 2011 (PSC 2011), 121-131, 2011.08. |
| 176. | Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, Proc. The Prague Stringology Conference 2011 (PSC 2011), 197-208, 2011.08. |
| 177. | Tomohiro I, Shunsuke Inenaga and Masayuki Takeda, Palindrome Pattern Matching, Proc. the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), LNCS 6661, 232-245, 2011.06. |
| 178. | Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, Proc. the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), LNCS 6661, 309-322, 2011.06. |
| 179. | Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen,, Finding Missing Patterns, Journal of Discrete Algorithms, 9, 2, 153-165, 2011.06. |
| 180. | Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, Veli Mäkinen, Missing pattern discovery, Journal of Discrete Algorithms, 10.1016/j.jda.2010.08.005, 9, 2, 153-165, 2011.06, In this paper, we study the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data. © 2010 Elsevier B.V. All rights reserved.. |
| 181. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, Password Based Anonymous Authentication with Private Information Retrieval, Journal of Digital Information Management, 9, 2, 72-78, 2011.04. |
| 182. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Anonymous Authentication Protocol with Single-database PIR, Proc. Australasian Information Security Conference 2011 (AISC 2011), CRPIT Series Vol. 116, 3-8, 2011.01. |
| 183. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting and Verifying Maximal Palindromes, Proc. the 17th Symposium on String Processing and Information Retrieval (SPIRE 2010), LNCS 6393, 135-146, 2010.10. |
| 184. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Identifiable yet Unlinkable Authentication System with Smart Cards for Multiple Services, IPSJ Transactions on Mathematical Modeling and its Applications, 3, 3, 54-66, 2010.10. |
| 185. | Shunsuke Inenaga, Kenichiro Oyama, and Hiroto Yasuura, Towards Modeling Stored-Value Electronic Money Systems, IPSJ Transactions on Mathematical Modeling and its Applications, 3, 3, 107-116, 2010.10. |
| 186. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Verifying a Parameterized Border Array in $O(n^{1.5})$ Time, Proc. the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010),, LNCS 6129, 238-250, 2010.06. |
| 187. | Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs, Chicago Journal of Theoretical Computer Science, Special Issue: CATS 2009, Article 4, 2010.06. |
| 188. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Identifiable yet Unlinkable Authentication System with Smart Cards for Multiple Services, Proc. The 2010 International Conference on Computational Science and Its Applications (ICCSA 2010), LNCS 6019, 236-251, 2010.03. |
| 189. | Heikki Hyyrö, Kazuyuki Narisawa, and Shunsuke Inenaga, Dynamic Edit Distance Table under a General Weighted Cost Function, Proc. 36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2010),, LNCS 5901, 515-527, 2010.01. |
| 190. | Shunsuke Inenaga, Kenichiro Oyama, and Hiroto Yasuura, Towards Modeling Stored-Value Electronic Money Systems, Proc. 8th International Conference on Computer Information Systems and Industrial Management Applications (CISIM 2009), 902-907, 2009.12. |
| 191. | Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara, Linear-Time text compression by longest-first substitution, Algorithms, 10.3390/a2041429, 2, 4, 1429-1448, 2009.12, We consider grammar-based text compression with longest first substitution (LFS), where non-overlapping occurrences of a longest repeating factor of the input text are replaced by a new non-terminal symbol. We present the first linear-time algorithm for LFS. Our algorithm employs a new data structure called sparse lazy suffix trees. We also deal with a more sophisticated version of LFS, called LFS2, that allows better compression. The first linear-time algorithm for LFS2 is also presented.. |
| 192. | Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Off-Line Text Compression by Longest-First Substitution, Algorithms, 2, 24, 1429-1448, 2009.11. |
| 193. | Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, Proc. The Prague Stringology Conference 2009 (PSC 2009), 40-54, 2009.08. |
| 194. | Tomohiro I, Satoshi Deguchi, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Lightweight Parameterized Suffix Array Construction, Proc. 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), LNCS 5874, 312-323, 2009.07. |
| 195. | Tomomi Yamasaki, Shunsuke Inenaga, Daisuke Ikeda, and Hiroto Yasuura, Modeling Costs of Access Control with Various Key Management Systems, Proc. The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2009), 676-682, 2009.07. |
| 196. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, Anonymous Authentication Systems Based on Private Information Retrieval, Proc. 1st International Conference on Networked Digital Technologies (NDT 2009), 53-58, 2009.07. |
| 197. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting Parameterized Border Arrays for a Binary Alphabet, Proc. 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), LNCS 5457, 422-433, 2009.04. |
| 198. | Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto, Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes, Theoretical Computer Science, 410, 8-10, 900-913, 2009.03. |
| 199. | Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto, Efficient algorithms to compute compressed longest common substrings and compressed palindromes, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2008.12.016, 410, 8-10, 900-913, 2009.03, This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n(4) log n) time with O(n(3)) space, and in O(n(4)) time with O(n(2)) space, respectively, where n is the size of the input SLP-compressed strings. (C) 2008 Elsevier B.V. All rights reserved.. |
| 200. | Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program, Proc. 15th Computing: The Australasian Theory Symposium (CATS 2009), CRPIT Series Vol. 94, 19-28, 2009.01. |
| 201. | Kazuyuki Narisawa, Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, and Masayuki Takeda, String Kernels Based on Variable-Length-Don't-Care Patterns, Proc. 11th International Conference on Discovery Science (DS 2008), LNAI 5255, 308-318, 2008.10. |
| 202. | Satoshi Deguchi, Fumihito Higashijima, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Parameterized Suffix Arrays for Binary Strings, Proc. The Prague Stringology Conference 2008 (PSC 2008), 84-94, 2008.09. |
| 203. | Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, International Journal of Foundations of Computer Science, 19, 1, 147-162, 2008.02. |
| 204. | Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Reachability on suffix tree graphs, INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 10.1142/S0129054108005590, 19, 1, 147-162, 2008.02, We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O(log n) time. Furthermore, we present a series of strings that require circle minus(n root n) time and space to answer reachability queries in O(log n) time for the same algorithm. Exhaustive computational calculations for strings of length n |
| 205. | Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto, Computing longest common substring and all palindromes from compressed strings, Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), LNCS 4910, 364-375, 2008.01. |
| 206. | Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), LNCS 4580, 340-351, 2007.07. |
| 207. | Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Simple Linear-Time Off-Line Text Compression by Longest-First Substitution, Proc. Data Compression Conference 2007 (DCC 2007), 123-132, 2007.03. |
| 208. | Shunsuke Inenaga and Masayuki Takeda, Sparse Directed Acyclic Word Graphs, 13th International Symposium on String Processing and Information Retrieval (SPIRE'06), Lecture Notes in Computer Science (LNCS4209), pp. 61-73, Springer-Verlag, 2006.10. |
| 209. | Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, A New Family of String Classifiers Based on Local Relatedness, Proc. 9th International Conference on Discovery Science (DS 2006), Lecture Notes in Artificial Intelligence (LNAI 4265), LNAI 4265, 114-124, 2006.10. |
| 210. | Shunsuke Inenaga and Masayuki Takeda, Sparse Compact Directed Acyclic Word Graphs, The Prague Stringology Conference '06 (PSC'06), pp. 195-211, Czech Technical University, 2006.08. |
| 211. | Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, The Prague Stringology Conference '06 (PSC'06), pp. 212-225, Czech Technical University, 2006.08. |
| 212. | Shunsuke Inenaga and Masayuki Takeda, On-line Linear-time Construction of Word Suffix Trees, 17th Annual Symposium on Combinatorial Pattern Matching (CPM'06), Lecture Notes in Computer Science (LNCS4009), pp. 60-71, Springer-Verlag, 2006.07. |
| 213. | Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, International Journal of Foundations of Computer Science, 10.1142/S0129054105003728, 16, 6, 1155-1166, 2005.12. |
| 214. | S Inenaga, A Shinohara, M Takeda, A fully compressed pattern matching algorithm for simple collage systems, INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 10.1142/S0129054105003728, 16, 6, 1155-1166, 2005.12, We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns am also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form , where D is a dictionary and S is a sequence of variables from 1). Our F(;PM algorithm performs in O(parallel to D parallel to(2) + mn log |S|) time, where n = |T| = parallel to D parallel to + |S| and m = |P|. This is faster than the previous best result of O(m(2)n(2)) time.. |
| 215. | Stanislav Angelov and Shunsuke Inenaga, Composite Pattern Discovery for PCR Application, 12th International Symposium on String Processing and Information Retrieval (SPIRE'05), Lecture Notes in Computer Science (LNCS3772), pp. 167-178, Springer-Verlag, 2005.11. |
| 216. | Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, and Masayuki Takeda, Practical Algorithms for Pattern Based Linear Regression, 8th International Conference on Discovery Science (DS'05), 3735, 44-56, Lecture Notes in Artificial Intelligence (LNAI3735), pp. 44-56, Springer-Verlag, 2005.10. |
| 217. | Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Fully Incremental LCS Computation, 15th International Symposium on Fundamentals of Computation Theory (FCT'05), 3623, 563-574, Lecture Notes in Computer Science (LNCS3623), pp. 563-574, Springer-Verlag, 2005.08. |
| 218. | Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi, On-Line Construction of Compact Directed Acyclic Word Graphs, Discrete Applied Mathematics, 10.1016/dam.2004.04.012, 146, 2, 156-179, 2005.03. |
| 219. | S Inenaga, H Hoshino, A Shinohara, M Takeda, S Arikawa, G Mauri, G Pavesi, On-line construction of compact directed acyclic word graphs, DISCRETE APPLIED MATHEMATICS, 10.1016/dam.2004.04.012, 146, 2, 156-179, 2005.03, Many different index structures, providing efficient solutions to problems related to pattern matching, have been introduced so far. Examples of these structures are suffix trees and directed acyclic word graphs (DAWGs), which can be efficiently constructed in linear time and space. Compact directed acyclic word graphs (CDAWGs) are an index structure preserving some features of both suffix trees and DAWGs, and require less space than both of them. An algorithm which directly constructs CDAWGs in linear time and space was first introduced by Crochemore and Verin, based on McCreight's algorithm for constructing suffix trees. In this work, we present a novel on-line linear-time algorithm that builds the CDAWG for a single string as well as for a set of strings, inspired by Ukkonen's on-line algorithm for constructing suffix trees. (C) 2004 Elsevier B.V. All rights reserved.. |
| 220. | Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars, Eighth International Conference on Developments in Language Theory (DLT'04), 3340, 225-236, Lecture Notes in Computer Science (LNCS3340), pp. 225-236, Springer-Verlag, 2004.12. |
| 221. | Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, Theoretical Compututer Science, 10.1016/j.tcs.2004.07.008, 328, 1-2, 97-111, 2004.11. |
| 222. | S Miyamoto, S Inenaga, M Takeda, A Shinohara, Ternary directed acyclic word graphs, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2004.07.008, 328, 1-2, 97-111, 2004.11, Given a set S of strings, a DFA accepting S offers a very time-efficient solution to the pattern matching problem over S. The key is how to implement such a DFA in the trade-off between time and space, and especially the choice of how to implement the transitions of each state is critical. Bentley and Sedgewick proposed an effective tree structure called ternary trees. The idea of ternary trees is to 'implant' the process of binary search for transitions into the structure of the trees themselves. This way the process of binary search becomes visible, and the implementation of the trees becomes quite easy. The directed acyclic word graph (DAWG) of a string w is the smallest DFA that accepts all suffixes of w, and requires only linear space. We apply the scheme of ternary trees to DAWGs, introducing a new data structure named ternary DAWGs (TDAWGs). Furthermore, the scheme of AVL trees is applied to the TDAWGs, yielding a more time-efficient structure AVL TDAWGs. We also perform some experiments that show the efficiency of TDAWGs and AVL TDAWGs, compared to DAWGs in which transitions are implemented by linked lists. (C) 2004 Elsevier B.V. All rights reserved.. |
| 223. | Shunsuke Inenaga, Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance, 7th International Conference on Discovery Science (DS 2004), 3245, 32-46, Lecture Notes in Artificial Intelligence (LNAI3245), pp. 32-46, Springer-Verlag, 2004.10. |
| 224. | Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen, Finding Missing Patterns, 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Bioinformatics (LNBI3240), pp. 461-474, Springer-Verlag, 2004.09. |
| 225. | Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, The Prague Stringology Conference '04 (PSC '04), 10.1142/S0129054105003728, 16, 6, 1155-1166, pp. 98-113, Czech Technical University, 2004.08. |
| 226. | Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, Efficiently finding regulatory elements using correlation with gene expression, Journal of Bioinformatics and Computational Biology, 2, 2, 273-288, 2004.06. |
| 227. | Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano, Efficiently finding regulatory elements using correlation with gene expression, Journal of Bioinformatics and Computational Biology, 10.1142/S0219720004000612, 2, 2, 273-288, 2004.06, We present an efficient algorithm for detecting putative regulatory elements in the upstream DNA sequences of genes, using gene expression information obtained from microarray experiments. Based on a generalized suffix tree, our algorithm looks for motif patterns whose appearance in the upstream region is most correlated with the expression levels of the genes. We are able to find the optimal pattern, in time linear in the total length of the upstream sequences. We implement and apply our algorithm to publicly available microarray gene expression data, and show that our method is able to discover biologically significant motifs, including various motifs which have been reported previously using the same data set. We further discuss applications for which the efficiency of the method is essential, as well as possible extensions to our algorithm. © Imperial College Press.. |
| 228. | Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, Journal of Discrete Algorithms, 2, 1, 33-51, 2004.03. |
| 229. | Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Compact directed acyclic word graphs for a sliding window, Journal of Discrete Algorithms, 10.1016/S1570-8667(03)00064-9, 2, 1, 33-51, 2004.03, Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string ω can be constructed in O(n) time and space, where n denotes the length of ω. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window. © 2003 Elsevier B.V. All rights reserved.. |
| 230. | Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Off-Line Text Compression by Longest-First Substitution, 10th International Symposium on String Processing and Information Retrieval (SPIRE 2003), 2857, 137-152, Lecture Notes in Computer Science (LNCS2857), pp. 137-152, Springer-Verlag, 2003.10. |
| 231. | Masayuki Takeda, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Setsuo Arikawa, Discovering Most Classificatory Patterns for Very Expressive Pattern Classes, The 6th International Conference on Discovery Science (DS 2003), 2843, 486-493, Lecture Notes in Artificial Intelligence (LNAI2843), pp. 486-493, Springer-Verlag, 2003.10. |
| 232. | Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Inferring Strings from Graphs and Arrays, 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), 2747, 208-217, Lecture Notes in Computer Science (LNCS2747), pp. 208-217, Springer-Verlag, 2003.08. |
| 233. | Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, Eighth International Conference on Implementation and Application of Automata (CIAA 2003, 2759, 120-130, Lecture Notes in Computer Science (LNCS2759), pp. 121-130, 2003.07. |
| 234. | Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, and Setsuo Arikawa, A Note on Randomized Algorithm for String Matching with Mismatches, Nordic Journal of Computing, 10, 1, 2-12, 2003.04. |
| 235. | Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, Nordic Journal of Computing, 10, 1, 52-67, 2003.04. |
| 236. | Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, A String Pattern Regression Algorithm and Its Application to Pattern Discovery in Long Introns, The 13th International Conference on Genome Informatics (GIW 2002), pp. 3-11, Universal Academy Press, 2002.12. |
| 237. | Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Discovering Best Variable-Length-Don't-Care Patterns, The Fifth International Conference on Discovery Science (DS '02), 2534, 86-97, Lecture Notes in Computer Science (LNCS2534), pp. 86-97, 2002.11. |
| 238. | Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, 9th International Symposium on String Processing and Information Retrieval (SPIRE 2002), Lecture Notes in Computer Science (LNCS 2476), pp. 310-324, 2002.09. |
| 239. | Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, and Setsuo Arikawa, A Note on Randomized Algorithm for String Matching with Mismatches, The Prague Stringology Conference '02 (PSC '02), pp. 9-17, Czech Technical University, 2002.09. |
| 240. | Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, The Prague Stringology Conference '02 (PSC '02), pp. 75-87, Czech Technical University, 2002.09. |
| 241. | Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, and Setsuo Arikawa, The Minimum DAWG for All Suffixes of a String and Its Applications, 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), 2373, 153-167, Lecture Notes in Computer Science (LNCS 2373), pp. 153-167, 2002.07. |
| 242. | Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs, 8th International Symposium on String Processing and Information Retrieval (SPIRE '01), 96-110, pp. 96-110, IEEE Computer Society, 2001.11. |
| 243. | Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Construction of the CDAWG for a Trie, The Prague Stringology Conference '01 (PSC '01), pp. 37-48, Czech Technical University, 2001.09. |
| 244. | Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, A Practical Algorithm to Find the Best Episode Patterns, The Fourth International Conference on Discovery Science (DS '01), Lecture Notes in Artificial Intelligence (LNAI 2226), pp. 435-440, 2001.11. |
| 245. | Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi, On-Line Construction of Compact Directed Acyclic Word Graphs, 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), 10.1016/dam.2004.04.012, 146, 2, 156-179, Lecture Notes in Computer Science (LNCS 2089), pp. 169-180, 2001.07. |
本データベースの内容を無断転載することを禁止します。
九大関連コンテンツ
QIR 九州大学学術情報リポジトリ システム情報科学研究院
システム情報科学研究院
- デバイスシミュレータを用いた論理回路のソフトエラー解析
- ハイブリッド環境下の大学図書館における学術情報サービスの構築
- A Run-Time Power Analysis Method using OS-Observable Parameters for Mobile Terminals
- Microwave-assisted magnetization reversal in a Co/Pd multilayer with perpendicular magnetic ...
- Modeling Costs of Access Control with Various Key Management Systems