# A lot of two way search...

• ``````class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
int len = s1.size();
if (len == 0) return 0;
vector<vector<int>> wordIndex = vector<vector<int>>(26, vector<int>());
for (int i = 0; i < len; ++i) {
int ch = s1[i] - 'a';
wordIndex[ch].push_back(i);
}
vector<vector<int>> nextIndex = vector<vector<int>>(26, vector<int>(100, -1));

std::function<int(int, int)> getNextIndex = [&](int index, int ch) {
if (index == len) {
index = 0;
}

if (nextIndex[ch][index] != -1) {
return nextIndex[ch][index];
}

int& ret = nextIndex[ch][index];
if (wordIndex[ch].size() == 0) {
ret = -2;
return ret;
}

int l = 0, r = wordIndex[ch].size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (index <= wordIndex[ch][mid]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}

if (l == wordIndex[ch].size()) {
l = wordIndex[ch][0];
}
else {
l = wordIndex[ch][l];
}

// Point to the next pos.
// if l == size, means we will start next.
l++;

ret = l;
return ret;
};

// Calculate the result.
unordered_map<int, int> startIndexSet;
vector<pair<int, int>> offset;
int start = 0;
while (true) {
if (startIndexSet.find(start) != startIndexSet.end()) {
// Find a loop.
break;
}

startIndexSet[start] = offset.size();

int cnt = 0;
for (int i = 0; i < s2.size(); ++i) {
int ch = s2[i] - 'a';
int nextStart = getNextIndex(start, ch);

// printf("%d %d\n", wordIndex[ch][0], nextIndex[ch][start]);
// cout << s2[i] << " " << start << " " << nextStart << endl;
if (nextStart == -2) return 0;
if (nextStart <= start) {
cnt++;
}

start = nextStart;
}

offset.push_back(pair<int, int>(start, cnt));
}

int startIndex = startIndexSet[start];
int t1 = 0;
for (int i = 0; i < startIndex; ++i) {
t1 += offset[i].second;
}

int t2 = 0;
for (int i = startIndex; i < offset.size(); ++i) {
t2 += offset[i].second;
}

// printf("%d %d %d\n", startIndex, t1, t2);

std::function<bool(int)> canDo = [&](int m) {
long long total = 1;
long long c2 = n2*m;
// printf("%lld\n", c2);
if (c2 < startIndex) {
for (int i = 0; i < c2; ++i) {
total += offset[i].second;
}

}

c2 -= startIndex;
total += t1;

total += t2 * (c2 / (offset.size() - startIndex));
int remain = c2 % (offset.size() - startIndex);
for (int i = 0; i < remain; ++i) {
total += offset[i + startIndex].second;
}

// printf("%lld %d %d\n", total, n1, m);
};

// Try to get the correct result of M.
int l = 0, r = 1;

while (canDo(r)) {
r *= 2;
}

while (l <= r) {
int mid = l + (r - l) / 2;
if (canDo(mid)) {
l = mid + 1;
}
else {
r = mid - 1;
}
}

if (r < 0) r = 0;
return r;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.