| 稲永 俊介（いねなが しゆんすけ） | データ更新日：2023.11.27 |
教授 ／
システム情報科学研究院
情報学部門
数理情報
| 1. | Yuki Yonemoto, Yuto Nakashima and Shunsuke Inenaga, Computing SEQ-IC-LCS of non-linear texts, 26th Prague Stringology Conference (PSC 2023), 2023.08. |
| 2. | Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga, On Sensitivity of Compact Directed Acyclic Word Graphs, 14th International Conference on Combinatorics on Words (WORDS 2023), 2023.06. |
| 3. | Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, Cristian Urbina, Bit Catastrophes for the Burrows-Wheeler Transform, 27th International Conference on Developments in Language Theory (DLT 2023), 2023.06. |
| 4. | Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Space-Efficient STR-IC-LCS Computation, 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), 2023.01. |
| 5. | Takuya Mieno, Mitsuru Funakoshi, Shunsuke Inenaga, Computing Palindromes on a Trie in Linear Time, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 2022.12. |
| 6. | Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno, Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions, 29th International Symposium on String Processing and Information Retrieval (SPIRE 2022), 2022.10. |
| 7. | Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga, Minimal Absent Words on Run-Length Encoded Strings, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 8. | Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama, RePair Grammars are the Smallest Grammars for Fibonacci Words, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 9. | Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura, Cartesian Tree Subsequence Matching, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 2022.06. |
| 10. | Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, and Shunsuke Inenaga, Position Heaps for Cartesian-tree Matching on Strings and Tries, 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 11. | Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, On the approximation ratio of LZ-End to LZ77, 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 12. | Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Common Rollercoasters, 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 13. | Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Grammar Index By Induced Suffix Sorting, 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), 2021.10. |
| 14. | Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, Counting Lyndon Subsequences, Prague Stringology Conference 2021 (PSC 2021), 2021.08. |
| 15. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Parameterized Suffix Tray, 12th International Conference on Algorithms and Complexity (CIAC 2021), 2021.05. |
| 16. | 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, 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), 2021.01. |
| 17. | Shunsuke Inenaga, Suffix Trees, DAWGs, and CDAWGs for Forward and Backward Tries, 14th Latin American Theoretical Informatics Symposium (LATIN 2020), 2021.01. |
| 18. | 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. |
| 19. | 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. |
| 20. | 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. |
| 21. | 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. |
| 22. | Shunsuke Inenaga, Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings, Prague Stringology Conference 2020 (PSC 2020), 2020.08. |
| 23. | 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), 2020.06, [URL]. |
| 24. | 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), 2020.06, [URL]. |
| 25. | Shunsuke Inenaga, Combinatorial algorithms for grammar-based text compression, Tutorial on a Special Topic Related Combinatorial Methods for String and Graph, 2020.03. |
| 26. | Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches, Data Compression Conference (DCC 2020), 2020.03. |
| 27. | Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-EC-LCS Computation, 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020, 2020.01, [URL], The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings A and B. More recently, a set of four constrained LCS problems (called generalized constrained LCS problem) were proposed by Chen and Chao [J. Comb. Optim, 2011]. In this paper, we consider the substring-excluding constrained LCS (STR-EC-LCS) problem. A string Z is said to be an STR-EC-LCS of two given strings A and B excluding P if, Z is one of the longest common subsequences of A and B that does not contain P as a substring. Wang et al. proposed a dynamic programming solution which computes an STR-EC-LCS in O(mnr) time and space where [Inf. Process. Lett., 2013]. In this paper, we show a new solution for the STR-EC-LCS problem. Our algorithm computes an STR-EC-LCS in time where denotes the set of distinct characters occurring in both A and B, and L is the length of the STR-EC-LCS. This algorithm is faster than the O(mnr)-time algorithm for short/long STR-EC-LCS (namely, or), and is at least as efficient as the O(mnr)-time algorithm for all cases.. |
| 28. | Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, 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, [URL], A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. A string w is called a minimal absent word (MAW) of T if w does not occur in T and any proper substring of w occurs in T. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string T. We first show how the set of MUSs can change in a sliding window over T, and present an-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over T. Our bounds improve on the previous results in Crochemore et al. (2017).. |
| 29. | 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, 2019.12, [URL], For a set D of documents and a positive integer d, a string w is said to be d-left-right maximal, if (1) w occurs in at least d documents in D, and (2) any proper superstring of w occurs in less than d documents. The left-right-maximal generic words problem is, given a set D of documents, to preprocess D so that for any string p and for any positive integer d, all the superstrings of p that are d-left-right maximal can be answered quickly. In this paper, we present an O(n log m) space data structure (in words) which answers queries in O(|p| + o log log m) time, where n is the total length of documents in D, m is the number of documents in D and o is the number of outputs. Our solution improves the previous one by Nishimoto et al. (PSC 2015), which uses an O(n log n) space data structure answering queries in O(|p| + r · log n + o · log2 n) time, where r is the number of right-extensions q of p occurring in at least d documents such that any proper right extension of q occurs in less than d documents.. |
| 30. | 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. |
| 31. | 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. |
| 32. | Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing runs on a trie, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 2019.06, [URL], A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where the endpoints of the path must be a descendant/ancestor of the other. For a trie with n edges, we show that the number of runs is less than n. We also show an O(n√log n log log n) time and O(n) space algorithm for counting and finding the shallower endpoint of all runs. We further show an O(n log n) time and O(n) space algorithm for finding both endpoints of all runs. We also discuss how to improve the running time even more.. |
| 33. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster queries for longest substring palindrome after block edit, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 2019.06, [URL], Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(ℓ + log log n) time, after a substring in T is replaced by a string of arbitrary length ℓ. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(ℓ + log n) time for each query.. |
| 34. | Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of overlapping Lempel-Ziv and Lyndon factorizations, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 2019.06, [URL], Lempel-Ziv (LZ) factorization and Lyndon factorization are well-known factorizations of strings. Recently, Kärkkäinen et al. studied the relation between the sizes of the two factorizations, and showed that the size of the Lyndon factorization is always smaller than twice the size of the non-overlapping LZ factorization [STACS 2017]. In this paper, we consider a similar problem for the overlapping version of the LZ factorization. Since the size of the overlapping LZ factorization is always smaller than the size of the non-overlapping LZ factorization and, in fact, can even be an O(log n) factor smaller, it is not immediately clear whether a similar bound as in previous work would hold. Nevertheless, in this paper, we prove that the size of the Lyndon factorization is always smaller than four times the size of the overlapping LZ factorization.. |
| 35. | Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga, Online algorithms for constructing linear-size suffix trie, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 2019.06, [URL], The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string T of length n has O(n) nodes and edges, and the string label of each edge is encoded by a pair of positions in T. Thus, even after the tree is built, the input text T needs to be kept stored and random access to T is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a “stand-alone” alternative to the suffix trees. Namely, the LST of a string T of length n occupies O(n) total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text T. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of T into the LST of T in O(nlog σ) time and O(n) space, where σ is the alphabet size. In this paper, we present two types of online algorithms which “directly” construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works in O(nlog σ) time and O(n) space and the left-to-right construction algorithm works in O(n(log σ + log n/log log n)) time and O(n) space. The main feature of our algorithms is that the input text does not need to be stored.. |
| 36. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Parameterized Position Heap of a Trie, 11th International Conference on Algorithms and Complexity (CIAC 2019), 2019.05. |
| 37. | Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida, MR-RePair Grammar Compression Based on Maximal Repeats, 2019 Data Compression Conference, DCC 2019, 2019.03, [URL], We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design a novel variant of RePair, called MR-RePair, which substitutes the most frequent maximal repeats at once instead of substituting the most frequent pairs consecutively. We implemented MR-RePair and compared the size of the grammar generated by MR-RePair to that by RePair on several text corpora. Our experiments show that MR-RePair generates more compact grammars than RePair does, especially for highly repetitive texts.. |
| 38. | Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compact Data Structures for Shortest Unique Substring Queries, 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019, 2019.01, [URL], Given a string T of length n, a substring 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.), and (c) every substring v of T with containing [s, t] occurs at least twice in T. Given a query interval, the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a bits data structure answering an interval SUS query in output-sensitive time, where is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for. Here, we propose a bits data structure answering a point SUS query in the same output-sensitive time.. |
| 39. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, 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.01, [URL], We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.. |
| 40. | Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka, On Longest Common Property Preserved Substring Queries, 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019, 2019.01, [URL], We revisit the problem of longest common property preserving substring queries introduced by Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line setting, where we are given a set X of k strings of total length n that can be pre-processed so that, given a query string y and a positive integer (Formula presented), we can determine the longest substring of y that satisfies some specific property and is common to at least (Formula presented) strings in X. Ayad et al. considered the longest square-free substring in an on-line setting and the longest periodic and palindromic substring in an off-line setting. In this paper, we give efficient solutions in the on-line setting for finding the longest common square, periodic, palindromic, and Lyndon substrings. More precisely, we show that X can be pre-processed in O(n) time resulting in a data structure of O(n) size that answers queries in (Formula presented) time and O(1) working space, where (Formula presented) is the size of the alphabet, and the common substring must be a square, a periodic substring, a palindrome, or a Lyndon word.. |
| 41. | Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest unique palindromic substring queries on run-length encoded strings, 30th International Workshop on Combinatorial Algorithms, IWOCA 2019, 2019.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 + m√log m/log logm) time so that all SUPSs for any subsequent query interval can be answered in O(√log m/log logm+ α) time, where α is the number of outputs, and σRLES is the number of distinct runs of RLES.. |
| 42. | Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Parameterized Position Heap of a Trie, 11th International Conference on Algorithms and Complexity, CIAC 2019, 2019.01, [URL], Let and be disjoint alphabets of respective size and. Two strings over of equal length are said to parameterized match (p-match) if there is a bijection such that (1) f is identity on and (2) f maps the characters of one string to those of the other string so that the two strings become identical. We consider the p-matching problem on a (reversed) trie and a string pattern P such that every path that p-matches P has to be reported. Let N be the size of the given trie. In this paper, we propose the parameterized position heap for that occupies O(N) space and supports p-matching queries in time, where m is the length of a query pattern P and is the number of paths in to report. We also present an algorithm which constructs the parameterized position heap for a given trie in time and working space.. |
| 43. | Keisuke Goto, I. Tomohiro, Hideo Bannai, Shunsuke Inenaga, Block palindromes A new generalization of palindromes, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, 2018.10, [URL], We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.. |
| 44. | Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, 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, [URL], The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor.. |
| 45. | 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. |
| 46. | Prague Stringology Conference 2018 (PSC 2018), Right-to-left Online Construction of Parameterized Position Heaps, Prague Stringology Conference 2018 (PSC 2018), 2018.08. |
| 47. | Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, Masayuki Takeda, Computing longest common square subsequences, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], A square is a non-empty string of form Y Y. The longest common square subsequence (LCSqS) problem is to compute a longest square occurring as a subsequence in two given strings A and B. We show that the problem can easily be solved in O(n6) time or O(|M|n4) time with O(n4) space, where n is the length of the strings and M is the set of matching points between A and B. Then, we show that the problem can also be solved in O(σ|M|3 + n) time and O(|M|2 + n) space, or in O(|M|3 log2 n log log n + n) time with O(|M|3 + n) space, where σ is the number of distinct characters occurring in A and B. We also study lower bounds for the LCSqS problem for two or more strings.. |
| 48. | Kotaro Aoyama, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster online elastic degenerate string matching, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], An Elastic-Degenerate String [Iliopoulus et al., LATA 2017] is a sequence of sets of strings, which was recently proposed as a way to model a set of similar sequences. We give an online algorithm for the Elastic-Degenerate String Matching (EDSM) problem that runs in O(nm √mlogm+ N) time and O(m) working space, where n is the number of elastic degenerate segments of the text, N is the total length of all strings in the text, and m is the length of the pattern. This improves the previous algorithm by Grossi et al. [CPM 2017] that runs in O(nm2 + N) time.. |
| 49. | Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest lyndon substring after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], The longest Lyndon substring of a string T is the longest substring of T which is a Lyndon word. LLS(T) denotes the length of the longest Lyndon substring of a string T. In this paper, we consider computing LLS(T′) where T′ is an edited string formed from T. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(log n) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of T is replaced by a given string of length l. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(l log σ + log n) time for any block edit where σ is the number of distinct characters in T. We can modify our algorithm so as to output all the longest Lyndon substrings of T′ for both problems.. |
| 50. | Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest substring palindrome after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], It is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log(min{ω, log n})) time after single character substitution, insertion, or deletion, where ω denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(ℓ+log n) time, after an existing substring in T is replaced by a string of arbitrary length ℓ.. |
| 51. | Isamu Furuya, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Lyndon factorization of grammar compressed texts revisited, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible.. |
| 52. | Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing abelian string regularities based on RLE, 28th International Workshop on Combinational Algorithms, IWOCA 2017, 2018.01, [URL], Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v1, …, vs of strings such that v1, …, vs-1 are all Abelian equivalent and vs is a substring of a permutation of v1, then w is said to have a regular Abelian period (p, t) where p = |v1| and t = |vs|. If a substring w1[i.i+l-1] of a string w1 and a substring w2[j.j + l - 1] of another string w2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w1 and w2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w1 and w2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w1 and w2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m2n) time.. |
| 53. | Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest unique palindromic substring queries in optimal time, 28th International Workshop on Combinational Algorithms, IWOCA 2017, 2018.01, [URL], 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.. |
| 54. | Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings, 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017.12. |
| 55. | Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon Puglisi, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09. |
| 56. | Tenma Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Order preserving pattern matching on trees and DAGs, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09. |
| 57. | Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga and Hiroki Arimura, Linear-size CDAWG: new repetition-aware indexing and grammar compression, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09. |
| 58. | Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, On Reverse Engineering the Lyndon Tree, Prague Stringology Conference 2017 (PSC 2017), 2017.08. |
| 59. | Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Small-space LCE data structure with constant-time queries, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017.08. |
| 60. | Hideo Bannai, Shunsuke Inenaga, Dominik Köppl, Computing All Distinct Squares in Linear Time for Integer Alphabets, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 61. | Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-IC-LCS computation via RLE, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 62. | Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tight bounds on the maximum number of shortest unique substrings, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07. |
| 63. | Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian string regularities based on RLE, 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07. |
| 64. | Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Palindromic Substring Queries in Optimal Time, 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07. |
| 65. | 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), 2017.01. |
| 66. | 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), 2017.01. |
| 67. | Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding gapped palindromes online, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 2016.08. |
| 68. | Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully dynamic data structure for LCE queries in compressed space, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08. |
| 69. | Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08. |
| 70. | Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Prague Stringology Conference 2016 (PSC 2016), 2016.08. |
| 71. | Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) time, Prague Stringology Conference 2016 (PSC 2016), 2016.08. |
| 72. | Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Efficiently Finding All Maximal α-gapped Repeats, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 2016.02. |
| 73. | Heikki Hyyrö, 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), 2016.01. |
| 74. | Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, 26th International Symposium on Algorithms and Computation (ISAAC 2015), 2015.12. |
| 75. | Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Waleń, Efficient Algorithms for Longest Closed Factor Array, 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09. |
| 76. | Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A faster algorithm for computing maximal α-gapped repeats in a string, 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09. |
| 77. | Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proc. Prague Stringology Conference 2015 (PSC 2015), 2015.08. |
| 78. | Shunsuke Inenaga, A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications, Proc. Prague Stringology Conference 2015 (PSC 2015), 2015.08. |
| 79. | 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, 19th International Conference on Developments in Language Theory (DLT 2015), 2015.07. |
| 80. | Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.06. |
| 81. | Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.06. |
| 82. | Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Factorizing a string into squares in linear time, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06. |
| 83. | Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06. |
| 84. | Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Fully-online construction of suffix trees for multiple texts, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06. |
| 85. | Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 2015.06. |
| 86. | Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, 9th International Conference on Algorithms and Complexity (CIAC 2015), 2015.05. |
| 87. | 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 動的な圧縮索引, LAシンポジウム 2014 冬, 2015.01. |
| 88. | 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, Lyndon ≦ LZ77 Conjecture, LAシンポジウム 2014 冬, 2015.01. |
| 89. | 青木 隆宏, 松岡 禎明, 稲永 俊介, 坂内 英夫, 竹田 正幸, 順序同型パターン照合アルゴリズム, LAシンポジウム 2014 冬, 2015.01. |
| 90. | 藤重 雄大, 稲永 俊介, 坂内 英夫, 竹田 正幸, 重複のない文字列における α-ギャップ repeat の列挙, LAシンポジウム 2014 冬, 2015.01. |
| 91. | 谷村 優佳, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列中にある極大α-gapped repeatの列挙, LAシンポジウム 2014 冬, 2015.01. |
| 92. | 中村 道太郎, 稲永 俊介, 坂内 英夫, 竹田 正幸, 固定長ギャップ付き回文のオンライン計算, LAシンポジウム 2014 冬, 2015.01. |
| 93. | 久保井 啓太, 稲永 俊介, 坂内 英夫, 竹田 正幸, 制約柔軟パターンを含む最長共通柔軟パターン問題, LAシンポジウム 2014 冬, 2015.01. |
| 94. | Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA 2015), 2015.01. |
| 95. | Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Prague Stringology Conference 2014 (PSC 2014), 2014.09. |
| 96. | Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian Covers and Abelian Runs, Prague Stringology Conference 2014 (PSC 2014), 2014.09. |
| 97. | Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), 2014.08. |
| 98. | 西田 真, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列のアーベル周期の逆問題について, 夏のLAシンポジウム2014, 2014.07. |
| 99. | 松田 奨平, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列のアーベル被覆とアーベル連, 夏のLAシンポジウム2014, 2014.07. |
| 100. | Tomohiro I, Shiho Sugimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), 2014.06. |
| 101. | Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014.03. |
| 102. | 杉本 志穂, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 回文による文字列の分解と被覆, 冬のLAシンポジウム2013, 2014.01. |
| 103. | 井 智弘, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, LZ78圧縮されたテキストに対するLyndon分解アルゴリズム, 冬のLAシンポジウム2013, 2014.01. |
| 104. | 玉腰 裕也, 後藤 啓介, 稲永 俊介, 坂内 英夫, 竹田 正幸, 連長圧縮と接尾辞配列について, 冬のLAシンポジウム2013, 2014.01. |
| 105. | 山本 淳一, 井 智弘, 坂内 英夫, 稲永 俊介, 竹田 正幸, 省スペースオンラインLZ分解, 冬のLAシンポジウム2013, 2014.01. |
| 106. | 松岡 禎明, 井 智弘, 坂内 英夫, 稲永 俊介, 竹田 正幸, 動的でコンパクトな索引構造, 冬のLAシンポジウム2013, 2014.01. |
| 107. | Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 2014.01. |
| 108. | Tomohiro I, Yuto Nakashima, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text, 20th Symposium on String Processing and Information Retrieval (SPIRE 2013), 2013.10. |
| 109. | Tomohiro I, Wataru Matsubara, Kouji Shimohira, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting Regularities on Grammar-compressed Strings, 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 2013.08. |
| 110. | Shiho Sugimoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, Prague Stringology Conference 2013 (PSC 2013), 2013.08. |
| 111. | 中島 祐人, 岡部 駿志, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, Lyndon分解の逆問題, 夏のLAシンポジウム2013, 2013.07. |
| 112. | 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, Sorting, Indexing, Computing LCE and LCP of SLP Compressed Strings, 夏のLAシンポジウム2014, 2013.07. |
| 113. | Tomohiro I, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Compressed Automata for Dictionary Matching, 18th International Conference on Implementation and Application of Automata (CIAA 2013), 2013.07. |
| 114. | Tomohiro I, Yuto Nakashima, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06. |
| 115. | Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga, Masayuki Takeda, Converting SLP to LZ78 in almost linear time, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06. |
| 116. | Yuya Tamakoshi, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, Data Compression Conference 2013 (DCC 2013), 2013.03. |
| 117. | Toshiya Tanaka, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing convolution on grammar-compressed text, Data Compression Conference 2013 (DCC 2013), 2013.03. |
| 118. | 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 高速パターン照合を可能にする新しい文法圧縮型自己索引, 冬のLAシンポジウム2012, 2013.01. |
| 119. | 西田 真, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 直線的プログラムに含まれる繰り返し構造の検出, 冬のLAシンポジウム2012, 2013.01. |
| 120. | 井 智弘, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, 圧縮テキスト上で動作するLyndon分解アルゴリズム, 冬のLAシンポジウム2012, 2013.01. |
| 121. | 杉本 志穂, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 逆向きLZ77分解のオンライン計算について, 冬のLAシンポジウム2012, 2013.01. |
| 122. | Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga, Permuted Pattern Matching on Multi-Track Strings, 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), 2013.01. |
| 123. | Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient LZ78 Factorization of Grammar Compressed Text, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |
| 124. | Yuto Nakashima, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, The Position Heap of a Trie, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |
| 125. | Yuto Nakashima, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, The Position Heap of a Trie, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |
| 126. | 田中 俊弥, 稲永 俊介, 坂内 英夫, 竹田 正幸, 圧縮テキストに対する畳み込み計算, 夏のLAシンポジウム2012, 2012.07. |
| 127. | 杉本 志穂, 稲永 俊介, 坂内 英夫, 竹田 正幸, 極小不在パターンの列挙アルゴリズム, 夏のLAシンポジウム2012, 2012.07. |
| 128. | 井 智弘, 稲永 俊介, 坂内 英夫, 直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム, 夏のLAシンポジウム2012, 2012.07. |
| 129. | 玉腰 裕也, 坂内 英夫, 稲永 俊介, 竹田 正幸, 木構造で表現された複数文字列に対する接尾辞配列の構築, 夏のLAシンポジウム2012, 2012.07. |
| 130. | 中島 祐人, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 木構造で表現された複数文字列に対するポジションヒープ, 夏のLAシンポジウム2012, 2012.07. |
| 131. | 山本 淳一, 稲永 俊介, 坂内 英夫, 竹田 正幸, 連長圧縮に基づくLZ77分解, 夏のLAシンポジウム2012, 2012.07. |
| 132. | Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Speeding-up q-gram mining on grammar-based compressed texts, 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), 2012.07. |
| 133. | Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), 2012.01. |
| 134. | Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), 2011.10. |
| 135. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, The Prague Stringology Conference 2011 (PSC 2011), 2011.08. |
| 136. | Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, The Prague Stringology Conference 2011 (PSC 2011), 2011.08. |
| 137. | Tomohiro I, Shunsuke Inenaga, Masayuki Takeda, Palindrome Pattern Matching, 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011.06. |
| 138. | Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011.06. |
| 139. | Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, Hiroto Yasuura, An Anonymous Authentication Protocol with Single-database PIR, Australasian Information Security Conference 2011 (AISC 2011), 2011.01. |
| 140. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Counting and Verifying Maximal Palindromes, 17th Symposium on String Processing and Information Retrieval (SPIRE 2010), 2010.10. |
| 141. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting and Verifying Maximal Palindromes, コンピュテーション研究会, 2010.09. |
| 142. | 井智弘，稲永俊介，坂内英夫，竹田正幸, Verifying a Parameterized Border Array in $O(n^{1.5})$ Time, 第9回情報科学技術フォーラム（FIT 2010）, 2010.09. |
| 143. | 稲永俊介，坂内英夫, Finding Characteristic Substrings from Compressed Texts, 夏のLAシンポジウム2010, 2010.07. |
| 144. | Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Verifying a Parameterized Border Array in O(n^{1.5}) Time, 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), 2010.06. |
| 145. | 成澤和志，Heikki Hyyrö，稲永俊介, 一般的な重みに対する編集距離の動的計算, 夏のLAシンポジウム2009, 2009.07. |
| 146. | 井智弘，出口悟史，坂内英夫，稲永俊介，竹田正幸, Lightweight Construction of Parameterized Suffix Arrays, 夏のLAシンポジウム2009, 2009.07. |
| 147. | Tomomi Yamasaki, Shunsuke Inenaga, Daisuke Ikeda, and Hiroto Yasuura, Modeling Costs of Access Control with Various Key Management Systems, 第74回数理モデル化と問題解決(MPS)研究会, 2009.07. |
| 148. | 松原渉，稲永俊介，篠原歩, 平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム, コンピュテーション研究会, 2009.03. |
| 149. | 中村徹，稲永俊介，馬場謙介，池田大輔，安浦寛人, マルチサービス環境における署名手法のリンク不能性に関する研究, 2009年暗号と情報セキュリティシンポジウム（SCIS2009）, 2009.01. |
| 150. | 中村徹，稲永俊介，馬場謙介，池田大輔，安浦寛人, プライバシ保護とメモリ効率性の両立を実現するマルチサービス環境向け認証方式, コンピュータセキュリティシンポジウム2008, 2008.10. |
| 151. | 松原渉，稲永俊介，石野明，篠原歩，中村智将，橋本和夫, 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム, コンピュテーション研究会, 2008.03. |
| 152. | 中村徹，稲永俊介，池田大輔，馬場謙介，安浦寛人, 認証システムのプライバシ保護評価のためのフレームワークの提案, 暗号と情報セキュリティシンポジウム (SCIS2008), 2008.01. |
| 153. | 中村徹，稲永俊介，馬場謙介，池田大輔，安浦寛人, プライバシ保護技術の評価のための権限認証モデル, コンピュータセキュリティシンポジウム2007 (CSS2007), 2007.10. |
| 154. | 小山健一郎，稲永俊介，安浦寛人, 電子マネーシステムの価値保存形式を考慮したモデル化, 第63回数理モデル化と問題解決(MPS)研究会, 2007.03. |
| 155. | Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, 第63回人工知能基本問題研究会, 2006.09. |
| 156. | 稲永俊介，竹田正幸, 単語接尾辞木再考, 第61回人工知能基本問題研究会, 2005.11. |
| 157. | 石田祐介，稲永俊介，篠原歩，竹田正幸, 漸増的最長共通部分列問題, 日本応用数理学会2005年度年会, 2005.09. |
| 158. | 稲永俊介，星野弘雅，篠原歩，竹田正幸，有川節夫, Unification of Algorithms to Construct Index Structures for Texts, 夏のLAシンポジウム2001, 2001.07. |
| 159. | 稲永俊介, 欠如パターン発見問題, 情報検索と発見科学に関する研究会, 2003.03. |
本データベースの内容を無断転載することを禁止します。
九大関連コンテンツ
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