Find minimum shift for longest common prefix in C++

Consider we have two strings A and B. The length of A and B are same. In a single shift we can rotate the string B one element. We have to find minimum required shift to get common prefix of maximum length from A and B. So if A = “computerprogramming”, and B = “programminglanguage” So the minimum shift is 8, and prefix is “programming”.

Suppose we add the string B at the end of B, so B = B + B, then there is no-need to find prefix of each shift separately. So we have to find the longest prefix of A present in B, and the starting position of the prefix in B, will give the actual number of required shifts.

Example

 Live Demo

#include<iostream> using namespace std; void KhuthMorrisPatt(int m, int n, string B, string A) {    int pos = 0, len = 0;    int p[m + 1];    int k = 0;    p[1] = 0;    for (int i = 2; i <= n; i++) {       while (k > 0 && A[k] != A[i - 1])          k = p[k];       if (A[k] == A[i - 1])          ++k;          p[i] = k;       }       for (int j = 0, i = 0; i < m; i++) {          while (j > 0 && A[j] != B[i])             j = p[j];          if (A[j] == B[i])             j++;          if (j > len) {             len = j;             pos = i - j + 1;          }    }    cout << "Shift = " << pos << endl;    cout << "Prefix = " << A.substr(0, len); } int main() {    string A = "programminglanguage";    string B = "computerprogramming";    int n = A.size();    B = B + B;    KhuthMorrisPatt(2 * n, n, B, A); }

Output

Shift = 8 Prefix = programming