【解析几何】 【多源路径】 【贪心】1520 最多的不重叠子字符串

//多源码路径
template<class T, T INF = 1000 * 1000 * 1000>
class CFloyd
{
public:
  CFloyd(const  vector<vector<T>>& mat)
  {
    m_vMat = mat;
    const int n = mat.size();
    for (int i = 0; i < n; i++)
    {//通过i中转
      for (int i1 = 0; i1 < n; i1++)
      {
        for (int i2 = 0; i2 < n; i2++)
        {
          //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
          m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
          //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
        }
      }
    }
  };
  vector<vector<T>> m_vMat;
};
template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  vector<string> maxNumOfSubstrings(string s) {
    vector<int> indexs[26];
    for (int i = 0; i < s.length(); i++)
    {
      indexs[s[i] - 'a'].emplace_back(i);
    }
    vector<vector<int>> mat(26, vector<int>(26,1000'000'000));
    for (int i = 0; i < 26; i++)
    {
      if (indexs[i].empty()) { continue; }      
      for (int j = 0; j < 26; j++)
      {
        auto it1 = std::lower_bound(indexs[j].begin(), indexs[j].end(), indexs[i].front());
        auto it2 = std::upper_bound(indexs[j].begin(), indexs[j].end(), indexs[i].back());
        if (it2 - it1 > 0 )
        {
          mat[i][j] = 1;
        }
      }
    }
    CFloyd floyd(mat);
    vector<pair<int, int>> rl;
    for (int i = 0; i < 26; i++)
    {     
      int left = 1000'000, r = -1;
      for (int j = 0; j < 26; j++)
      {
        if (floyd.m_vMat[i][j] < 1000'000'000)
        {
          MinSelf(&left, indexs[j].front());
          MaxSelf(&r, indexs[j].back());
        }
      }
      if (-1 == r)
      {
        continue;
      }
      rl.emplace_back(r, left);
    }
    sort(rl.begin(), rl.end());
    int end = -1;
    vector<string> vAns;
    for (const auto& [r, left] : rl)
    {
      if (left > end)
      {
        vAns.emplace_back(s.substr(left, r - left + 1));
        end = r;
      }
    }
    return vAns;
  }
  
};

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 = "cabcccbaa";
    auto res = sln.maxNumOfSubstrings(s);
    Assert({ "cabcccbaa" }, res);
  }
  {
    Solution sln;
    s = "ababa";
    auto res = sln.maxNumOfSubstrings(s);
    Assert({ "ababa" }, res);
  }
  {
    Solution sln;   
    s = "adefaddaccc";
    auto res = sln.maxNumOfSubstrings(s);
    Assert({ "e","f","ccc" }, res);
  }
  
  {
    Solution sln;
    s = "abbaccd";
    auto res = sln.maxNumOfSubstrings(s);
    Assert({ "bb","cc","d" }, res);
  }
}