子串专题
poj2406（连续重复子串）
题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
poj3261（可重复k次的最长子串）
题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
spoj705( 求不相同的子串个数)
题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin
【UVA】10066-The Twin Towers（最长公共子串问题）
赤裸裸的最长公共子串问题，没什么好说的，注意的是，每组数据后面都有一个空行。 13996019 10066 The Twin Towers Accepted C++ 0.015 2014-08-06 00:34:53 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using
MySQL中的`SUBSTRING()`和`MID()`函数：精准抽取字符串中的子串
在数据库操作中，经常需要从存储的字符串中提取出特定的部分，比如从用户全名中提取姓氏、从日期字符串中提取年份等。MySQL提供了SUBSTRING()和MID()两个函数，它们的功能几乎完全相同，都是用来从字符串中抽取子串的。本文将详细介绍这两个函数的用法、参数以及在实际场景中的应用。 一、SUBSTRING()和MID()函数的基本语法 1. SUBSTRING()函数 SUBSTRING(
leetcode： 5. 最长回文子串
5. 最长回文子串 题目链接https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
java常用算法之最长回文子串(Longest Palindromic Substring)
方法一：时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i
【LeetCode】03.无重复字符的最长子串
题目要求 做题链接3.无重复字符的最长子串 解题思路 我们通过参考给出的输入很容易就会从每一个字符开始，看看最长能延续多长。我们通过画图发现一旦一个字符可以延续到另一个字符，那么我们就不需要考虑他中间仍然存在字符重复的问题。因此而后我们发现可以使用滑动窗口进行优化。 代码实现 class Solution {public:int lengthOfLongestSubstring(s
3、无重复字符的最长子串
题目 链接：leetcode链接 思路分析（滑动窗口） 子串是连续的，很容易联想到滑动窗口，处理连续子串问题很方便。 先设置left和right两个指针，从0位置开始移动。 为了去判断窗口里面有没有出现重复的子串，可以使用一个hash表来存出现的次数， 这里为了防止有些小伙伴不会用hash表，就先用数组模拟一下hash表吧。 当hash表里面没出现right字符时，就插入hash表，r
第八届蓝桥杯 最大公共子串（动态规划）
标题：最大公共子串 最大公共子串长度问题就是： 求两个串的所有子串中能够匹配上的最大长度是多少。 比如："abcdkkk" 和 "baabcdadabc"， 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。 请分析该解法的思路，并补全划线部分缺失的代码。 #include <stdio.h
后缀数组 - 求最长回文子串 + 模板题 --- ural 1297
1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim
【hot100篇-python刷题记录】【最长回文子串】
R7-多维dp篇 思路： 两种情况，中心1个数，中心2个数 大体：中间点扩展原则 class Solution:def expand(self,s,left,right):while left>=0 and right<len(s) and s[left]==s[right]:left-=1right+=1#不满足就回退return left+1,right-1def longe
探索C++编程技巧：计算两个字符串的最长公共子串
探索C++编程技巧：计算两个字符串的最长公共子串 在C++面试中，考官通常会关注候选人的编程能力、问题解决能力以及对C++语言特性的理解。一个常见且经典的问题是计算两个字符串的最长公共子串（Longest Common Substring, LCS）。本文将详细介绍如何编写一个函数来解决这个问题，并深入探讨相关的编程技巧和优化方法。 目录 引言问题描述解决思路实现步骤 基础实现动态规划优化代
【最新华为OD机试E卷】最左侧冗余覆盖子串(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)
🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 ｜ 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测，专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.
Leetcode每日刷题之76.最小覆盖子串(C++)
1.题目解析 本题的题目是给定两个字符串 s 和 t ，找出在 s 中的某个最小子串保证该子串中包含所以 t 中出现的字母即可，并且该结果是唯一答案，找不到结果就直接返回空串即可 2.算法原理 关于本题的核心思路就是"滑动窗口"，具体实现是： 1.首先给定两个指针left和right，使用count统计窗口内有效字符的种类，之所以不是有效字符的个数是因为在最小子串中只要完全包含t中
算法练习题10：leetcode76最小覆盖子串-滑动窗口
目录 题目 题目描述 约束条件 解决思路 代码 getOrDefault(c, 0) 方法 方法签名 参数 返回值 示例 getOrDefault 与 get 的主要区别 Integer 题目 题目描述 给定两个字符串 s 和 t，请你在字符串 s 中找到包含 t 中所有字符的最小子串。 要求： 如果 s 中存在这样一个子串，返回这个最小
【编程题】最长公共连续子串
牛牛有两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述: 输入为两行字符串（可能包含空格），长度均小于等于50. 输出描述: 输出为一个整数，表示最长公共连续子串的长度。 输入例子: abcdeabgde 输出例子: 2 #include <iostream>#include <string.h>#include <
判断母串是否包含子串的某种排列
1. 题目 给出两个字符串s1 和 s2，判断s2 是否 包含s1的某种排列，如果是，返回True，否则返回False。 输入：s1=‘ab’， s2 = “qwebaei” 输出：True 输入：s1=‘abc’， s2 = “qwebaei” 输出：False 2. 分析 这是一道面试题，要在15min内解决，也并非那么容易。 2.1 贪心思想 我的思想是：某种排列的形态可以用字典
2024.9.2 Python，用栈写每日温度，等差数列划分，子串所有可能性，等差数列划分，深度优先搜索解决累加数
1.每日温度 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2: 输入
算法-------无重复字符的最长子串（Java版）
题目： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"
LintCode 最长无重复字符的子串
给定一个字符串，请找出其中无重复字符的最长子字符串。 例如，在”abcabcbb”中，其无重复字符的最长子字符串是”abc”，其长度为 3。 对于，”bbbbb”，其无重复字符的最长子字符串为”b”，长度为1。 从左向右扫描，遇到重复的字符时，从前面出现该字符的位置的下一个字符开始，重新扫描，直到扫描到最后。例如： abcbdefgdk 字符abcbdefgdk下标0123456789
LintCode 最长回文子串
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。 样例 给出字符串 “abcdzdcab”，它的最长回文子串为 “cdzdc”。 挑战 O(n2) 时间复杂度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。 第一次AC的连O（n2）都不是的，是O（n3），遍历所有子串。代码如下： class Solution:"""@
leetcode 76:最小覆盖子串
这道题我使用了很笨的方式花了好久解决了，但是时间复杂度太度，只看网上查看源码，不得不说网上的答案基本都是一样的，但是对于基础相对薄弱的我来说这些代码看起来很是费劲，还用要加强C++基础的练习才行。 思路相对来说不是很难： 1 首先构架t字符串的hash表，因为字符与ASCII码较好的关系，使用vector数组map来构造hash表，所存的int型表
算法练习题07：无重复字符的最长子串
我们可以使用 滑动窗口 的方法来解决这个问题。这是一种高效的算法，能在 O(n) 的时间复杂度内完成任务。以下是具体的解题思路： 1. 滑动窗口的概念 滑动窗口的想法是使用两个指针（通常称为左指针 i 和右指针 j）来表示一个窗口。这两个指针在字符串上滑动，以找到满足条件的子串。在这个问题中，我们的目标是找到最长的、没有重复字符的子串。 窗口的定义：窗口是由左指针 i 和右指针 j 所包