【字符串】【分类讨论】【KMP】1163. 按字典序排在最后的子串

2024-03-09 10:04

本文主要是介绍【字符串】【分类讨论】【KMP】1163. 按字典序排在最后的子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

视频算法专题

本文涉及知识点

字符串 字典序 分类讨论
本题无法使用KMP,因为t1不段变化。

LeetCode1163. 按字典序排在最后的子串

给你一个字符串 s ,找出它的所有子串并按字典序排列,返回排在最后的那个子串。
示例 1:
输入:s = “abab”
输出:“bab”
解释:我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。
示例 2:
输入:s = “leetcode”
输出:“tcode”
提示:
1 <= s.length <= 4 * 105
s 仅含有小写英文字符。

KMP

令s[0,i)的最后子串是t1,s[0,i]的最后子串t2。则t2一定以s[i],结尾,因为t1+s[i]一定在t1后面。
{ 从 t 1 取 0 个字符, t 2 = s [ i ] s [ i ] > t [ 0 ] 从 t 1 取后 m 个字符 t [ i − m , i ) + s [ i ] 条件下面详述 \begin{cases} 从t1取0个字符,t2 = s[i] & s[i] > t[0] \\ 从t1取后m个字符 t[i-m,i)+s[i] &条件下面详述\\ \end{cases} {t10个字符,t2=s[i]t1取后m个字符t[im,i)+s[i]s[i]>t[0]条件下面详述
t1[0,m) 不会小于 t[i-m,i),否则t1就是t[n-m,m)。
如果两种是大于关系,则t1[0,m]大于 t[i-m,i)+s[i] ,不成立。
故一定是相等关系,且t1[m]小于s[i]。
可以利用KMP的公共前后缀。
如果以上情况都不符合,则t2 = t1 + s[i]。
如果使用KMP,t1不断变化,时间复杂度是O(nn),超时。

分类讨论

令n = s.length()。
性质一:令s[x,y)是最后的子串,x ∈ \in [0,n)则y=n。因为s[x,n)的字典序比s[x,y)大。
性质二:令s[i,n)在s[x,n)中的字典序最大,x ∈ \in [0,j)。确保:j > i。
令s[i,i+k)和s[j,j+k)相等,下标 j+K非法, s[i+k]!=s[j+k]。初始:i=0,j=1,k=0
{ k + + s [ i + k ] = = s [ j + k ] k = 0 , i = j , j + + s [ i + k ] < s [ j + k ] 待证明一 k = 0 , i + = k + 1 s [ i + k ] > s [ j + k ] 待证明二 \begin{cases} k++ & s[i+k]==s[j+k] \\ k=0,i=j,j++& s[i+k] < s[j+k] & 待证明一\\ k=0,i+= k+1 & s[i+k] > s[j+k] & 待证明二\\ \end{cases} k++k=0,i=j,j++k=0,i+=k+1s[i+k]==s[j+k]s[i+k]<s[j+k]s[i+k]>s[j+k]待证明一待证明二

待证明一

显然s[j,n)的字典序大于s[i,n)结合性质二,s[j,n)是 s[x,n)中的最大字典序,x ∈ \in [0,j+1)。

待证明二

令x ∈ \in [j,j+k] ,则len = x - j+1 。
s[x,n)的字典序小于s[i+len,n),结合性质二,s[i+len,n)小于s[i],s[x,n)小于s[i,n)。现在来证明无后效性:
从小到处理len,则:
s[0,j+len)符合性质二,由于s[0,i+len]符合性质二。

超时

多余n-1个a,后面跟一个b。时间复杂度O(nn)。

代码

核心代码

class Solution {
public:string lastSubstring(string s) {int i = 0;for (int j = 1; j < s.length(); ){int k = 0;for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);int tmp = i;if (s[i + k] < s[j + k]){i = j++;}else{j += k + 1;}			}return s.substr(i);}
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{string s ;{Solution sln;s = "cacacb";auto res = sln.lastSubstring(s);Assert("cb", res);}{Solution sln;s = "abab";auto res = sln.lastSubstring(s);Assert("bab", res);}{Solution sln;s = "leetcode";auto res = sln.lastSubstring(s);Assert("tcode", res);}}

优化

极端情况下,i=j++,执行了n次,k也为n。故时间复杂度为O(nn)。
分两种情况:
一,i+k <= j 不变。
二,i+k > j。下面具体分析:
令m = j-i。
将s[j,j+k)和s[i,i+k)分成若干块,最后一块长度为k%m,前面的块长度都为m,则:
s[j,j+k)的各块分别为:s[j,i) s[i,i+m) s[i+m,i+m2) ⋯ \cdots
s[i,i+k)的个块分别为:s[i,i+m) s[i+m,i+m
2) ⋯ \cdots
→ \rightarrow s[j,i) == s [i,i+m) == s[i+m,i+m*2) ⋯ \cdots
显然s[j,n)淘汰了s[i,n)
x$\in[0,m)
s[j,n)能够淘汰s[j+n,n) 因为s[i,n)删除前m个字符,s[i+x,n)删除就是两者。
同理:s[j+m,n)能淘汰s[j]和s[j+m+x,n)。
⋮ \vdots
故 i =j + k - (k%m) ⟺ \iff i+m+k - (k%m)
因为 m > k%m ,所以 i+m+k - (k%m) > i+ k,也就i至少增加k。
无论什么情况:
i或j至少有一个至少增加k,故总时间复杂度是O(n)。

代码

class Solution {
public:string lastSubstring(string s) {int i = 0;for (int j = 1; j < s.length(); ){int k = 0;for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);int tmp = i;if (s[i + k] < s[j + k]){const int m = j - i;if (k > m){i = (j + k - k%m);j = i + 1;}else{i = j++;}}else{j += k + 1;}			}return s.substr(i);}
};

2023年5月版

class Solution {
public:
string lastSubstring(string s) {
int iMaxIndex = 0;
for (int i = 1; i < s.length(); i++)
{
int k = 0;
for (; (i + k < s.length()) && (s[i + k] == s[iMaxIndex + k]); k++)
{
}
if ((i + k < s.length()) && (s[i + k] > s[iMaxIndex + k]))
{
auto tmp = iMaxIndex;
iMaxIndex = i;
i = max(i,tmp+k);
}
else
{
i = i + k ;
}
}
return s.substr(iMaxIndex);
}
};

2024年2月版

class Solution {
public:
string lastSubstring(string s) {
int i = 0;
for (int j = 1; j < s.length(); )
{
int k = 0;
for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);
int tmp = i;
if (s[i + k] < s[j + k])
{
const int m = j - i;
if (k > m)
{
i += k+1;
j = i + 1;
}
else
{
i = j++;
}
}
else
{
j += k + 1;
}
}
return s.substr(i);
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【字符串】【分类讨论】【KMP】1163. 按字典序排在最后的子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/790336

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回(flashback)功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回(flashb

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字