【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数

//最长公共前缀(Longest Common Prefix)
class CLCP
{
public:
  CLCP(const string& str1, const string& str2)
  {
    m_dp.assign(str1.length() , vector<int>(str2.length()));
    //str1[j...)和str2[k...]比较时, j和k不断自增，总有一个先到达末端
    for (int i = 0; i < str1.length(); i++)
    {//枚举str2 先到末端 str1[i]和str2.back对应
      m_dp[i][str2.length() - 1] = (str1[i] == str2.back());
      for (int j = i-1 ; j >= 0 ; j-- )
      {
        const int k = str2.length() - 1 - (i-j);
        if (k < 0)
        {
          break;
        }
        if (str1[j] == str2[k])
        {
          m_dp[j][k] = 1 + m_dp[j + 1][k + 1];
        }
      }     
    }
    for (int i = 0; i < str2.length(); i++)
    {//枚举str1 先到末端 str2[i]和str1.back对应
      m_dp[str1.length()-1][i] = (str1.back() == str2[i]);
      for (int j = i - 1; j >= 0; j--)
      {
        const int k = str1.length() - 1 - (i-j);
        if (k < 0)
        {
          break;
        }
        if (str1[k] == str2[j])
        {
          m_dp[k][j] = 1 + m_dp[k + 1][j + 1];
        }
      }
    }
  }
  vector<vector<int>> m_dp;
};
template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
class Solution {
public:
  int numberOfCombinations(string num) {
    m_c = num.length();
    CLCP lcp(num, num);
    vector<vector<C1097Int<> >> dp(m_c + 1, vector<C1097Int<> >(m_c + 1));
    dp[0][0] = 1;
    for (int i = 0; i < m_c; i++)
    {
      if ('0' == num[i])
      {
        continue;
      }
      C1097Int biSum = 0;
      for (int j = 1; i + j <= m_c; j++)
      {
        biSum += dp[i][j - 1];
        dp[i + j][j] += biSum;
        bool bMoreEqual = false;
        if ((i >= j))
        {
          const int len = lcp.m_dp[i][i - j];
          if (len  >= j)
          {
            bMoreEqual = true;
          }
          else
          {
            bMoreEqual = num[i + len] > num[i - j + len];
          }
        }
        if (bMoreEqual)
        {
          dp[i + j][j] += dp[i][j];
        }
      }
    }
    return std::accumulate(dp.back().begin(), dp.back().end(), C1097Int()).ToInt();
  }
  int m_c;
};

template<class T>
void Assert(const T& t1, const T& 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 num;
  {
    Solution sln;
    num = "327";
    auto res = sln.numberOfCombinations(num);
    Assert(res,2);
  }
  {
    Solution sln;
    num = "094";
    auto res = sln.numberOfCombinations(num);
    Assert(res, 0);
  }
  {
    Solution sln;
    num = "0";
    auto res = sln.numberOfCombinations(num);
    Assert(res, 0);
  }
  {
    Solution sln;
    num = "9999999999999";
    auto res = sln.numberOfCombinations(num);
    Assert(res, 101);
  }
}