C++ | Most Unique Solution | Binary Lifting
Obviously for every character of $S_2$, there must be a character in $S_1$, otherwise we can never make an answer, therefore, in this case, the answer is $0$.\n
Obviously for every character of $S_2$, there must be a character in $S_1$, otherwise we can never make an answer, therefore, in this case, the answer is $0$.\n\nOtherwise, imagine a graph, where for every $i \\in S_1$ and $j \\in S_2$ if $S_1[i]=S_2[j]$ then we make one node.\n\nNow from a certain node $(i_1,j_1)$ there will be an **exactly** one outgoing edge to $(i_2,j_2)$.\n\nThis is a propery of a [Functional Graph](https://usaco.guide/silver/func-graphs), and we can use Binary Lifting to solve this problem.\n\nWe can make an edge with weight $1$ if we made a cycle from $S_1$, we can also make an additional edge with weight $1$ if we made a cycle from $S_2$.\n\nBy using Binary Lifting, we can get, for $N_1$ cycle of $S_1$ how many cycles will we have for $S_2$, suppose it\'s $X$.\n\nNow the answer is simply $\\frac{X}{N_2}$.\n\n# Complexity\n\n\n- Time complexity: $O(|S_1||S_2|\\log N_2))$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(|S_1||S_2|\\log N_2)$ \n\n# Code\n```cpp []\nconst int N = 105;\nconst int K = 30;\nconst int A = 26;\n\npair<int, int> up[K][N][N];\nint d1[K][N][N];\nint d2[K][N][N];\n\nclass Solution {\npublic:\n    int getMaxRepetitions(string s1, int n1, string s2, int n2) {\n        int n = (int) s1.size();\n        int m = (int) s2.size();\n        vector<set<int>> st1(A);\n        for (int i = 0; i < n; i++) {\n            int x = s1[i] - \'a\';\n            st1[x].emplace(i);\n        }\n        vector<set<int>> st2(A);\n        for (int i = 0; i < m; i++) {\n            int x = s2[i] - \'a\';\n            st2[x].emplace(i);\n        }\n        for (int cc = 0; cc < A; cc++) {\n            if (!st2[cc].empty() && st1[cc].empty()) {\n                return 0;\n            }\n        }\n        for (int cc = 0; cc < A; cc++) {\n            if (st2[cc].empty()) {\n                continue;\n            }\n            for (int j : st2[cc]) {\n                int nxt = j + 1;\n                if (nxt == m) {\n                    nxt = 0;\n                }\n                int cur = s2[nxt] - \'a\';\n                for (int i : st1[cc]) {\n                    auto it = st1[cur].upper_bound(i);\n                    if (it == st1[cur].end()) {\n                        it = st1[cur].begin();\n                    }\n                    int pos = *it;\n                    up[0][i][j] = {pos, nxt};\n                    d1[0][i][j] = pos <= i ? 1 : 0;\n                    d2[0][i][j] = nxt <= j ? 1 : 0;\n                }\n            }\n        }\n        for (int k = 1; k < K; k++) {\n            for (int cc = 0; cc < A; cc++) {\n                if (st2[cc].empty()) {\n                    continue;\n                }\n                for (int j : st2[cc]) {\n                    for (int i  : st1[cc]) {\n                        auto [i2, j2] = up[k - 1][i][j];\n                        up[k][i][j] = up[k - 1][i2][j2];\n                        d1[k][i][j] = d1[k - 1][i][j] + d1[k - 1][i2][j2];\n                        d2[k][i][j] = d2[k - 1][i][j] + d2[k - 1][i2][j2];\n                    }\n                }\n            }\n        }\n        int val = s2[0] - \'a\';\n        int si = *st1[val].begin();\n        int sj = *st2[val].begin();\n        int dist2 = 0;\n        for (int k = K - 1; k >= 0; k--) {\n            if (d1[k][si][sj] >= n1) {\n                continue;\n            }\n            n1 -= d1[k][si][sj];\n            dist2 += d2[k][si][sj];\n            tie(si, sj) = up[k][si][sj];\n        }\n        dist2 += d2[0][si][sj];\n        return dist2 / n2;\n    }\n};\n```
['C++']