Search

Your search keyword '"Nakashima, Yuto"' showing total 303 results
Start Over Author "Nakashima, Yuto"

Refine your results

more »

more »

more »

more »
303 results on '"Nakashima, Yuto"'

54. Longest Common Rollercoasters

Author

Fujita, Kosuke, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Lecroq, Thierry, editor, and Touzet, Hélène, editor

Published
2021
Full Text
View/download PDF

55. The Parameterized Suffix Tray

Author

Fujisato, Noriki, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Calamoneri, Tiziana, editor, and Corò, Federico, editor

Published
2021
Full Text
View/download PDF

56. On the Size of Lempel-Ziv and Lyndon Factorizations

Author

Kärkkäinen, Juha, Kempa, Dominik, Nakashima, Yuto, Puglisi, Simon J., and Shur, Arseny M.

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics
Abstract

Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing the structure and complexity of strings, but their combinatorial structure is very different. In this paper, we establish the first direct connection between the two by showing that while the Lyndon factorization can be bigger than the non-overlapping LZ factorization (which we demonstrate by describing a new, non-trivial family of strings) it is never more than twice the size., Comment: 12 pages

Published
2016
Full Text
View/download PDF

57. Shortest unique palindromic substring queries in optimal time

Author

Nakashima, Yuto, Inoue, Hiroe, Mieno, Takuya, Inenaga, Shunsuke, Bannai, Hideo, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

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 ($\mathit{SUPS}$) for an interval $[x, y]$ in $S$, if $P$ occurs exactly once in $S$, this occurrence of $P$ contains interval $[x, y]$, and every palindromic substring of $S$ which contains interval $[x, y]$ and is shorter than $P$ occurs at least twice in $S$. The $\mathit{SUPS}$ problem is, given a string $S$, to preprocess $S$ so that for any subsequent query interval $[x, y]$ all the $\mathit{SUPS}\mbox{s}$ for interval $[x, y]$ 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 $\mathit{SUPS}\mbox{s}$ for any subsequent query interval can be answered in $O(k+1)$ time, where $k$ is the number of outputs.

Published
2016

60. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

Author

Mieno, Takuya, Kuhara, Yuki, Akagi, Tooru, Fujishige, Yuta, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chatzigeorgiou, Alexander, editor, Dondi, Riccardo, editor, Herodotou, Herodotos, editor, Kapoutsis, Christos, editor, Manolopoulos, Yannis, editor, Papadopoulos, George A., editor, and Sikora, Florian, editor

Published
2020
Full Text
View/download PDF

62. Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets

Author

Nakashima, Yuto, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

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.

Published
2015

65. The 'Runs' Theorem

Author

Bannai, Hideo, I, Tomohiro, Inenaga, Shunsuke, Nakashima, Yuto, Takeda, Masayuki, and Tsuruta, Kazuya

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms
Abstract

We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture (Kolpakov \& Kucherov (FOCS '99)), which states that the maximum number of runs $\rho(n)$ in a string of length $n$ is less than $n$. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of $3n$ for the maximum sum of exponents $\sigma(n)$ of runs in a string of length $n$, improving on the best known bound of $4.1n$ by Crochemore et al. (JDA 2012), as well as other improved bounds on related problems. The characterization also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-Period Query problem that was recently solved by Kociumaka et al. (SODA 2015)., Comment: simple proof with some more bounds

Published
2014
Full Text
View/download PDF

67. Compact Data Structures for Shortest Unique Substring Queries

Author

Mieno, Takuya, Köppl, Dominik, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Brisaboa, Nieves R., editor, and Puglisi, Simon J., editor

Published
2019
Full Text
View/download PDF

68. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings

Author

Watanabe, Kiichi, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Colbourn, Charles J., editor, Grossi, Roberto, editor, and Pisanti, Nadia, editor

Published
2019
Full Text
View/download PDF

69. Efficient Lyndon factorization of grammar compressed text

Author

I, Tomohiro, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in $O(n^4 + mn^3h)$ time and $O(n^2)$ space, where $m$ is the size of the Lyndon factorization, $n$ is the size of the SLP, and $h$ is the height of the derivation tree of the SLP. Since the length of the decompressed string can be exponentially large w.r.t. $n, m$ and $h$, our result is the first polynomial time solution when the string is given as SLP., Comment: CPM 2013

Published
2013

75. Longest Common Rollercoasters

Author

Fujita, Kosuke, primary, Nakashima, Yuto, additional, Inenaga, Shunsuke, additional, Bannai, Hideo, additional, and Takeda, Masayuki, additional

Published
2021
Full Text
View/download PDF

76. Shortest Unique Palindromic Substring Queries in Optimal Time

Author

Nakashima, Yuto, Inoue, Hiroe, Mieno, Takuya, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brankovic, Ljiljana, editor, Ryan, Joe, editor, and Smyth, William F., editor

Published
2018
Full Text
View/download PDF

77. Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays

Author

Kuhara, Yuki, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Gagie, Travis, editor, Moffat, Alistair, editor, Navarro, Gonzalo, editor, and Cuadros-Vargas, Ernesto, editor

Published
2018
Full Text
View/download PDF

86. Longest Common Abelian Factors and Large Alphabets

Author

Badkobeh, Golnaz, Gagie, Travis, Grabowski, Szymon, Nakashima, Yuto, Puglisi, Simon J., Sugimoto, Shiho, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Inenaga, Shunsuke, editor, Sadakane, Kunihiko, editor, and Sakai, Tetsuya, editor

Published
2016
Full Text
View/download PDF

93. Optimal LZ-End Parsing Is Hard

Author

Hideo Bannai and Mitsuru Funakoshi and Kazuhiro Kurita and Yuto Nakashima and Kazuhisa Seto and Takeaki Uno, Bannai, Hideo, Funakoshi, Mitsuru, Kurita, Kazuhiro, Nakashima, Yuto, Seto, Kazuhisa, Uno, Takeaki, Hideo Bannai and Mitsuru Funakoshi and Kazuhiro Kurita and Yuto Nakashima and Kazuhisa Seto and Takeaki Uno, Bannai, Hideo, Funakoshi, Mitsuru, Kurita, Kazuhiro, Nakashima, Yuto, Seto, Kazuhisa, and Uno, Takeaki

Abstract

LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occurrence must end at the end of a previous phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is determined greedily from left to right, as the longest factor that satisfies the above constraint [Kreft & Navarro, 2010]. In this work, we consider an optimal LZ-End parsing that has the minimum number of phrases in such parsings. We show that a decision version of computing the optimal LZ-End parsing is NP-complete by showing a reduction from the vertex cover problem. Moreover, we give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach for computing various NP-hard repetitiveness measures recently presented by [Bannai et al., 2022]. We also consider the approximation ratio of the size of greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a lower bound of the ratio which asymptotically approaches 2.

Published
2023
Full Text
View/download PDF

94. Inferring Strings from Lyndon Factorization

Author

Nakashima, Yuto, Okabe, Takashi, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

95. Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text

Author

I, Tomohiro, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kurland, Oren, editor, Lewenstein, Moshe, editor, and Porat, Ely, editor

Published
2013
Full Text
View/download PDF

96. The Position Heap of a Trie

Author

Nakashima, Yuto, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Calderón-Benavides, Liliana, editor, González-Caro, Cristina, editor, Chávez, Edgar, editor, and Ziviani, Nivio, editor

Published
2012
Full Text
View/download PDF

100. Space-Efficient STR-IC-LCS Computation

Author

Yonemoto, Yuuki, Nakashima, Yuto, Inenaga, Shunsuke, and Bannai, Hideo

Subjects
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
Abstract

One of the most fundamental method for comparing two given strings $A$ and $B$ is the longest common subsequence (LCS), where the task is to find (the length) of the longest common subsequence. In this paper, we address the STR-IC-LCS problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string $Z$ is said to be an STR-IC-LCS of three given strings $A$, $B$, and $P$, if $Z$ is one of the longest common subsequences of $A$ and $B$ that contains $P$ as a substring. We present a space efficient solution for the STR-IC-LCS problem. Our algorithm computes the length of an STR-IC-LCS in $O(n^2)$ time and $O((\ell+1)(n-\ell+1))$ space where $\ell$ is the length of a longest common subsequence of $A$ and $B$ of length $n$. When $\ell = O(1)$ or $n-\ell = O(1)$, then our algorithm uses only linear $O(n)$ space.

Published
2022
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results