You can calculate the autocorrelation function of a sequence. Then, with one run, find out at what amount of shift the autocorrelation function takes the value equal to the sum of the squares of the sequence numbers (remember that char has a numerical representation, don't forget to convert the letters to int, so as not to overflow).
If, at least at one point, the autocorrelation function takes this value (by the way, it will be the maximum of this function), then one sequence is a cyclic shift of the other, and the magnitude of the required shift will be exactly the k in which the autocorrelation is maximum.
Let us estimate the complexity of the algorithm. Autocorrelation can be calculated using the fast discrete Fourier transform (we turn the second sequence over, and then we consider the convolution). This will take O (nlogn), then one run: O (n), total O (nlogn).
The second option. We take the second line s2, assign it to itself s2 + s2, then do a search for the string s1 in the string s2 + s2, this can be done using the Knut-Morris-Pratt algorithm for O (n) (by counting the prefix function , or by counting the Z-function ), if there is an entry, then the answer is "yes", and the index of entry is the magnitude of the desired cyclic shift. The final complexity is O (n), I think this algorithm is asymptotically optimal.
Further implementation in c ++. If you want to think for yourself, do not read the code. Everything has been done, with the possible exception of minor errors such as I / O (the search functions have been accurately tested, the rest have not been tested).
The implementation of the asymptotics O (n), the implementation through the Fourier transform is too lazy to do, it is more complicated and there is more code :)
#include <string> #include <vector> template<class T> std::vector<int> z_function(const T& str) { int n = str.size(); std::vector<int> answer(n, 0); int l, r; l = 0; r = 1; for (int i = 1; i < n; ++i) { if (i < r) { answer[i] = std::min(r - i, answer[i - l]); } while ( ( i + answer[i] < n ) && ( str[answer[i]] == str[i + answer[i]]) ) { ++answer[i]; } if ( i + answer[i] > r) { l = i; r = i + answer[i]; } } return answer; } template<class T> std::vector<int> search_kmp(const T& pattern, const T& text, const T& marker = T("#")) { std::vector<int> zf = z_function(pattern + marker + text); int ps = pattern.size(); int ts = text.size(); std::vector<int> answer; answer.reserve(ts); for (int i = 0; i + ps - 1 < text.size(); ++i) { if (zf[i + ps + 1] == ps) { answer.push_back(i); } } return answer; } int main() { int N; std::string str1, str2; std::cin >> N; std::cin >> str1; std::cin >> str2; std::string str(str2+str2); std::vector<int> mas = search_kmp(str1, str); if (!mas.empty()) { std::cout << mas[0] << std::endl; } else { std::cout << -1 << std::endl; } return 0; }
