后缀数组(Suffix Array)

本文介绍后缀数组的定义与构建的过程。首先,文章介绍什么是后缀数组,随后讲解了最自然的朴素算法。为了引出更高效的算法,文章提及了倍增思想与基数排序的背景基础知识。接着,通过模拟演练的方式一步一步地演示如何创建后缀数组。将构建的抽象过程形象地展示出来,使读者更易理解。定义给定字符串,其所有后缀有。(6为字符串的长度)。如下所示S = "banana"s1 = "banana"s2 = "anana"s3 = "nana"s4 = "ana"s5 = "na"s6 = "a"后缀数组即为由构成的有序的(字典序升序排列的)字符串数组。vector<string> sa{"a", "ana", "anana", "banana", "na", "nana"};构建后缀数组的动态过程演示动画: https://visualgo.net/zh/suffixarra思路如何构建后缀数组?若字符串的长... Read More

[LeetCode]893. Groups of Special-Equivalent Strings

原题You are given an array A of strings.Two strings S and T are special-equivalent if after any number of moves, S == T.A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.Return the number of groups o... Read More

[LeetCode]Valid Palindrome II

原题Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.Example 1Input: "aba"Output: TruExample 2Input: "abca"Output: TruExplanation: You could delete the character 'c'.NoteThe string will only contain lowercase characters a-z. The maximum length of the string is 50000.思路水题。判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近(双指针),如下代码[code lang="cpp"for (in... Read More