【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II

class KMP
{
public:
  virtual int Find(const string& s, const string& t)
  {
    CalLen(t);
    m_vSameLen.assign(s.length(), 0);
    for (int i1 = 0, j = 0; i1 < s.length(); )
    {
      for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
      //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
      m_vSameLen[i1] = j;
      //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
      if (0 == j)
      {
        i1++;
        continue;
      }
      const int i2 = i1 + j;
      j = m_vLen[j - 1];
      i1 = i2 - j;//i2不变
    }
    for (int i = 0; i < m_vSameLen.size(); i++)
    {//多余代码是为了增加可测试性
      if (t.length() == m_vSameLen[i])
      {
        return i;
      }
    }
    return -1;
  }
  vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性
protected:
  void CalLen(const string& str)
  {
    m_vLen.resize(str.length());
    for (int i = 1; i < str.length(); i++)
    {
      int next = m_vLen[i - 1];
      while (str[next] != str[i])
      {
        if (0 == next)
        {
          break;
        }
        next = m_vLen[0];
      }
      m_vLen[i] = next + (str[next] == str[i]);
    }
  }
  int m_c;
  vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 
};

class Solution {
public:
  vector<int> beautifulIndices(string s, string a, string b, int k) {
    KMP kmpa, kmpb;
    kmpa.Find(s, a);
    kmpb.Find(s, b);
    vector<int> bindex;
    for (int i = 0; i < kmpb.m_vSameLen.size(); i++)
    {
      if (kmpb.m_vSameLen[i] == b.length())
      {
        bindex.emplace_back(i);
      }
    }
    vector<int> vRet;
    for (int i = 0; i < kmpa.m_vSameLen.size(); i++)
    {
      if (kmpa.m_vSameLen[i] == a.length())
      {
        auto it1 = std::lower_bound(bindex.begin(), bindex.end(), i - k);
        auto it2 = std::upper_bound(bindex.begin(), bindex.end(), i + k);
        if (it2 - it1 > 0)
        {
          vRet.emplace_back(i);
        }
      }
    }
    return vRet;
  }
};

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 a,b,s;
  int k;
  {
    Solution sln;
    s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15;
    auto res = sln.beautifulIndices(s, a, b, k);
    Assert(vector<int>{16, 33}, res);
  }
  {
    Solution sln;
    s = "abcd", a = "a", b = "a", k = 4;
    auto res = sln.beautifulIndices(s, a, b, k);
    Assert(vector<int>{0}, res);
  }
}