substrings专题

CodeForces 386C Diverse Substrings

题意：一个字符串的价值等于它包含的不同字母的个数（abcdabcdabcd 的价值为4）给你一个字符串求该字符串所有子串的价值输出最大的价值是多少再分别输出价值为x的字符串有多少个思路： MAXstringlen=3*10^5 数据较大所以我首先尝试可否从左到右扫描一遍每次添加一个字符的想法但是最简单的加一个字符回头判断一下价值为x的字符串增加了多少个复杂

CodeForces 451D Count Good Substrings

题意：一个只包含a和b的字符串问它有几个长度为偶数和长度为奇数的“压缩回文串” 压缩的概念是相邻的相同字符压缩成一个字符思路：串经过压缩一定满足如下形式 ……ababab…… 那么这样只要两端的字符相同则中间一定是回文的因此对于一个a它作为左端点形成的回文串个数就等于它右边的a的个数那么长度是奇数还是偶数呢可以这么判断如果a在奇数位置上和它匹配的a也在奇

hdu 4455 Substrings(树状数组+递推)

题目链接：hdu 4455 Substrings 题目大意：给定一个长度为N的序列，现在有Q次询问，每次给定一个w，表示长度，输出序列中长度为w的连续子序列的权值和。序列的权值表示序列中不同元素的个数。解题思路：递推，先预处理处每个位置和前面相同的数据的最短距离P。dp[i]表示说长度为i子序列的权值和，dp[i+1] = dp[i] + v - c。v为[i+1~N]中P

hdu 1238 Substrings（KMP）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1238 求个公共字串，正逆序其中一个满足即可。 KMP暴力即可。判断的时候正逆序都去判断即可代码： #include <stdio.h>#include <string.h>const int N = 105;#define max(a,b) ((a)>(b)?(a):(b))char

UVA 10829 - L-Gap Substrings(后缀数组)

UVA 10829 - L-Gap Substrings 题目链接题意：一个字符串如果形如UGU，的形式，G的长度为L，那么称这个字符串为L串，给定一个字符串，问这个字符串子串为g串的个数思路：做这题前先做了POJ3693，有一个思想就是枚举长度分段，这样的话对于一个U长度为l的而言，只要在当前位置和当前位置之后(l + g)的位置分别向前向后找lcp，两个lcp加起来的长度减去

spoj694/705 Distinct Substrings - 后缀数组

题目链接：http://acm.hust.edu.cn/vjudge/problem/19282 题目大意：求不同子串的个数解题思路：后缀数组.. suffix(i)对子串个数所做的贡献为len-sa[i]+1，因为要求要不同的，所以减去与它串重复的子串个数h[i]。即每个后缀对答案的贡献为len-sa[i]+1-h[i];(***) #include<cstdio>#incl

2019湖南省赛 C.Distinct Substrings（哈希+二分，扩展KMP）

思路：串的最后加上i以后，实际上加上了 n + 1 n+1 n+1个串，我们要减去重复的子串个数。假设串加上 i i i后，对于长度为 m i d mid mid的后缀发生重复，那么对于长度为 1... m i d − 1 1...mid-1 1...mid−1的后缀也会发生重复，所以要判断有 m i d mid mid个重复子串，实际就是判断新串长度为 m i d mid mid的后缀和

Leetcode 3084. Count Substrings Starting and Ending with Given Character

Leetcode 3084. Count Substrings Starting and Ending with Given Character 1. 解题思路2. 代码实现题目链接：3084. Count Substrings Starting and Ending with Given Character 1. 解题思路这一题其实挺简单的，只要看一下目标的character在stri

POJ 3415 Common Substrings

Common Substrings Time Limit: 5000MS Memory Limit: 65536KTotal Submissions: 13775 Accepted: 4616 Description A substring of a string T is defined as: T(i, k)=TiTi+1...Ti+k-1, 1≤i≤i+k-1≤|T|.

LeetCode467. Unique Substrings in Wraparound String——动态规划

文章目录一、题目二、题解一、题目 We define the string base to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so base will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnop

B. Diverse Substrings (2024.1.22灵茶)

链接 : Problem - 1748B - Codeforces 思路 : 0-9一共十个字符，由于一个子串是diverse要满足每个字符出现的次数，不超过子串字符种类的数目，所以子串最长的情况也就是0-9每个10个，长度为100,所以可以暴力枚举所有子串；详情请看代码 : 代码: #include<bits/stdc++.h>#define IOS io

LeetCode2696. Minimum String Length After Removing Substrings

文章目录一、题目二、题解一、题目 You are given a string s consisting only of uppercase English letters. You can apply some operations to this string where, in one operation, you can remove any occurrence

Leetcode 1190. Reverse Substrings Between Each Pair of Parentheses [Python]

考察stack的典型题目。 class Solution:def reverseParentheses(self, s: str) -> str:stack = []temp = [] def reverse(string):res = []for i in range(len(string)-1, -1, -1):res.append(string[i])return ''.jo

Linecode 1870 · Number of Substrings with All Zeroes [Python]

每一段连续的0 有多少全0substring呢？观察计算可知是其长度N的连续加和至0，也就是N + N-1 + N-2 。。。。+ 1 class Solution:"""@param str: the string@return: the number of substrings """def stringCount(self, string):# Write your code here.p

SPOJ - DISUBSTR Distinct Substrings

1.题面 http://www.spoj.com/problems/DISUBSTR/en/ 2.题意问一个字符串中有多少个不同的子串 3.思路参考《后缀数组罗穗蹇》中的思路，很好写 4.代码 /*****************************************************************> File Name: Cpp_Acm.c

Leetcode 2949. Count Beautiful Substrings II

Leetcode 2949. Count Beautiful Substrings II 1. 解题思路2. 代码实现 Leetcode 2949. Count Beautiful Substrings II 1. 解题思路这一题真的很丢脸，居然没有搞定，是看了大佬们的思路之后才想明白的，就感觉丢脸丢大了…… 这道题讲道理挺简单的，而且相似类型的题目其实以前做过挺多的了，想不通但是为啥没

SPOJ DISUBSTR Distinct Substrings（后缀数组）

题意：一个字符串有多少个不同的字串思路：一个字符串共有 n∗(n+1)2 \frac{ n*(n+1) }{2}个，减去所有的height数组的值，就是减去了所有重复的子串错误及反思：代码： #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 101

SPOJ SUBST1 New Distinct Substrings（后缀数组）

题意：一个字符串有多少个不同的字串思路：题意与思路和 SPOJ DISUBSTR完全相同，唯一不同是数据范围，用后缀数组复杂度完全够，注意下long long 即可错误及反思：代码： #include<bits/stdc++.h>using namespace std;const int N=50000+10;int sa[N],rak[N],height[N];ch

Leetcode 1016. Binary String With Substrings Representing 1 To N解题报告(python)

1016. Binary String With Substrings Representing 1 To N Binary String With Substrings Representing 1 To N python solution 题目描述 Given a binary string S (a string consisting only of ‘0’ and '1’s) and