An α-gapped repeat (α ≥ 1) in a word w is a factor uvu of w such that |u v| ≤ α|u|; the two occurrences of u are called arms of this α-gapped repeat. An α-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character 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. In the case of α-gapped palindromes, i.e., factors \(uv{{u}^{\intercal }}\) with |u v|≤ α|u|, we show that the number of all maximal α-gapped palindromes occurring in words of length n is upper bounded by 28α n + 7n. Both upper bounds allow us to construct algorithms finding all maximal α-gapped repeats and/or all maximal α-gapped palindromes of a word of length n on an integer alphabet of size \(n^{\mathcal {O}(1)}\) in \({\mathcal {O}(\alpha n)}\) time. The presented running times are optimal since there are words that have Θ(α n) maximal α-gapped repeats/palindromes.

In this study, we propose a simple and effective preprocessing method for subword segmentation based on a data compression algorithm. Compression-based subword segmentation has recently attracted significant attention as a preprocessing method for training data in neural machine translation. Among them, BPE/BPE-dropout is one of the fastest and most effective methods compared to conventional approaches; however, compression-based approaches have a drawback in that generating multiple segmentations is difficult due to the determinism. To overcome this difficulty, we focus on a stochastic string algorithm, called locally consistent parsing (LCP), that has been applied to achieve optimum compression. Employing the stochastic parsing mechanism of LCP, we propose LCP-dropout for multiple subword segmentation that improves BPE/BPE-dropout, and we show that it outperforms various baselines in learning from especially small training data.

For the feature selection problem, we propose an efficient privacy-preserving algorithm. Let D, F, and C be data, feature, and class sets, respectively, where the feature value $x\left(F_i\right)$ and the class label $x\left(C\right)$ are given for each $x\in D$ and $F_i\in F$. For a triple $(D,F,C)$, the feature selection problem is to find a consistent and minimal subset $F^{\prime }\subseteq F$, where ‘consistent’ means that, for any $x,y\in D$, $x\left(C\right)=y\left(C\right)$ if $x\left(F_i\right)=y\left(F_i\right)$ for $F_i\in F^{\prime }$, and ‘minimal’ means that any proper subset of $F^{\prime }$ is no longer consistent. On distributed datasets, we consider feature selection as a privacy-preserving problem: assume that semi-honest parties $\mathsf{A}$ and $\mathsf{B}$ have their own personal $D_{\mathsf{A}}$ and $D_{\mathsf{B}}$. The goal is to solve the feature selection problem for $D_{\mathsf{A}}\cup D_{\mathsf{B}}$ without sacrificing their privacy. In this paper, we propose a secure and efficient algorithm based on fully homomorphic encryption, and we implement our algorithm to show its effectiveness for various practical data. The proposed algorithm is the first one that can directly simulate the CWC (Combination of Weakest Components) algorithm on ciphertext, which is one of the best performers for the feature selection problem on the plaintext.

Given a string T of length n whose characters are drawn from an ordered alphabet of size $$\sigma $$σ , its longest Lyndon subsequence is a maximum-length subsequence of T that is a Lyndon word. We propose algorithms for finding such a subsequence in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$O ( n 3 ) time with $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n)$$O ( n ) space, or online in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$O ( n 3 ) space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length at most n in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^4 \sigma )$$O ( n 4 σ ) time using $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^2)$$O ( n 2 ) space.