【字符串】【分类讨论】【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 * 10⁵

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 ] 条件下面详述

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

待证明一

显然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+m2) ⋯ \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++**实现。