Copy of snippet "second"

Snippet Exchange
1

t int m = primary.size();
int n = secondary.size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = 0;

for (int i = 1; i <= m; i++) {

dp[i][0] = dp[i-1][0];

for (int k = 0; k < i-1; k++) {
if (primary[k] > primary[i-1]) dp[i][0]++;
}
}


for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j-1];
for (int k = 0; k < j-1; k++) {
if (secondary[k] > secondary[j-1]) dp[0][j]++;
}
}


vector<int> invP(m + 1, 0);
for (int i = 1; i <= m; i++) {
invP[i] = invP[i-1];
for (int k = 0; k < i-1; k++) {
if (primary[k] > primary[i-1]) invP[i]++;
}
}


vector<int> invS(n + 1, 0);
for (int j = 1; j <= n; j++) {
invS[j] = invS[j-1];
for (int k = 0; k < j-1; k++) {
if (secondary[k] > secondary[j-1]) invS[j]++;
}
}


vector<vector<int>> greaterInPrimary(m + 1, vector<int>(26, 0));
for (int i = 1; i <= m; i++) {
for (int c = 0; c < 26; c++)
greaterInPrimary[i][c] = greaterInPrimary[i-1][c];
for (int c = 0; c < (primary[i-1] - 'a'); c++)
greaterInPrimary[i][c]++;
}


vector<vector<int>> greaterInSecondary(n + 1, vector<int>(26, 0));
for (int j = 1; j <= n; j++) {
for (int c = 0; c < 26; c++)
greaterInSecondary[j][c] = greaterInSecondary[j-1][c];
for (int c = 0; c < (secondary[j-1] - 'a'); c++)
greaterInSecondary[j][c]++;
}


for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {


int crossConflictP = greaterInSecondary[j][primary[i-1] - 'a'];
if (dp[i-1][j] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[i-1][j] + crossConflictP);


int crossConflictS = greaterInPrimary[i][secondary[j-1] - 'a'];
if (dp[i][j-1] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[i][j-1] + crossConflictS);
}
}

return dp[m][n] + invP[m] + invS[n];