466. 统计重复个数

466. 统计重复个数

题解
反正做法就是题解的意思，看完题解自己写的，可读性可能不高

class Solution {
 public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    int i1 = 0, idx = 0, cnt2 = 0, s1cnt = -1, head = -1, s2cnt;
    int end;
    map<int, pair<int, int>> mp;  // idx2 -> s1cnt,s2cnt
    for (int i = 0; i < n1; i++) {
      for (int i1 = 0; i1 < s1.size(); i1++) {
        if (s1[i1] == s2[idx]) idx++;
        if (idx == s2.size()) cnt2++, idx = 0;
      }
      pair<int, int> cur = make_pair(i, cnt2);
      if (mp.count(idx)) {
        pair<int, int> pre = mp[idx];
        s1cnt = cur.first - pre.first;
        s2cnt = cur.second - pre.second;
        head = pre.first + 1;
        end = idx;
        break;
      }
      mp[idx] = cur;
    }
    if (s1cnt == -1) return cnt2 / n2;
    int res = (n1 - head) / s1cnt * s2cnt;
    int headnum = cnt2 - s2cnt;
    res += headnum;
    int rest = n1 - head - (n1 - head) / s1cnt * s1cnt;
    // idx = (end + 1) % (int)s2.size();
    cnt2 = 0;
    for (int i = 0; i < rest; i++) {
      for (int i1 = 0; i1 < s1.size(); i1++) {
        if (s1[i1] == s2[idx]) idx++;
        if (idx == s2.size()) {
          res++;
          idx = 0;
        }
      }
    }
    return res / n2;
  }
};

class Solution {
 public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    int idx = 0, cnt2 = 0, s1cnt = -1, head = -1, s2cnt;
    map<int, pair<int, int>> mp;  // idx -> s1cnt, s2cnt
    for (int i = 0; i < n1; i++) {
      for (int i1 = 0; i1 < s1.size(); i1++) {
        if (s1[i1] == s2[idx]) idx++;
        if (idx == s2.size()) cnt2++, idx = 0;
      }
      pair<int, int> cur = make_pair(i, cnt2);
      if (mp.count(idx)) {
        pair<int, int> pre = mp[idx];
        s1cnt = cur.first - pre.first;
        s2cnt = cur.second - pre.second;
        head = pre.first + 1; // 这个地方一定要注意。。被坑了调半天，head是前面的数量
        break;
      }
      mp[idx] = cur;
    }
    if (s1cnt == -1) return cnt2 / n2;
    int res = (n1 - head) / s1cnt * s2cnt;
    int rest = n1 - head - (n1 - head) / s1cnt * s1cnt;
    idx = 0, cnt2 = 0;
    for (int i = 0; i < head + rest; i++) {
      for (int i1 = 0; i1 < s1.size(); i1++) {
        if (s1[i1] == s2[idx]) idx++;
        if (idx == s2.size()) {
          res++;
          idx = 0;
        }
      }
    }
    return res / n2;
  }
};