... continued from the other post of mine as we exceeded the 8000 characters limit.
I've got a few notes here too.
Though the program has comments that (somewhat) help, not everything is commented properly (e.g. what exactly is lcs -- longest common sequence? --, what does it do). Other times trivial things are commented (e.g. string s, t;) such comments are not helpful. :)
Variable names x, y, i, j, k, v1, etc are again poor choices as their names convey not much meaning. Most of the time it is more important of what we store in a variable than references to the type of the variable (as most IDEs can help with the latter).
What does it do?
Enough of those complaints. Let's see what the code does:
There are 3 functions here:
- main(): to drive the program, gets the user input and prints the output
- lcs(): It seems to be a longest common sequence implementation, i.e., finding character sequences in order (but may potentially skip characters) that are in the same order in both input strings
- check(): it is meant to verify that the found solution for the problem is a product of the two input strings of this method.
- vector<int> &v1: a proposed solution to check
- string &t: one of the strings build from the solution
- string &s: the other string build from the solution
What it does:
Checks if the two input strings are fully used up if one takes the indices from the proposed solution vector.
In my opinion, this is an overcomplicated function. All it should do is just check if both of the input strings (s, t) are fully processed, i.e., the relevant indices reached the end of both of the strings.
check() iterates through the string s via index i and separates s into two other strings x and y, depending on if the vector v1's next element (v1[j]) is matching the value of index i.
Then the function iterates through the string t via index j, and steps over every element in y if it is contained by t in the same order.
In the end, if the index k (denoting the last march index of y[k] == t[j]) is the same as the length of the string y, then every character is processed, we have a valid solution in the input vector v1.
- string &s: an input string of a possible combination of X and Y yielding one specific X Y
- string &t: another input string of a possible combination of X and Y yielding one(other) specific X Y
- vector<int> arr: the solution vector
- int idx1: the last processed index in s
- int idx2: the last processed index in t
What it does:
Tries to create a solution vector (arr) that lists the indices where s[idx1] and t[idx2] match.
Being a backtrack function, it should have a step that stops the recursion. And indeed, the first condition serves this purpose: if either input strings are at its end it calls check() to verify the validity of the proposed solution vector. If the proposed solution vector (arr) checks out good, the solution is set (ans = arr;) and the function returns true. Otherwise, false is returned (without setting the solution).
And now, the recursive part comes. If the next elements in the input strings match (s[idx1] == t[idx2]) the last checked index of string s is added to the proposed solution vector (arr.push_back(idx1);) and we call lcs() again by both indices incremented and return whatever value this provides.
If the above condition failed and did not enter the body of the if, then we return with calling lcs() first by incrementing the left index, then, if the left path failed, by incrementing the right index.
The above recursive logic traverses the entirety of both s and t strings and produces a proposed solution vector arr.
It reads two input strings (t, s), that are both supposed to be a combination of X and Y, i.e., a valid X Y.
lcs() is called to try to find a valid X and Y input strings that resulted in two X Y: t and s. If it is not possible, a message is printed and the program exits (return 0;).
If an lcs() can be acquired, then the X and Y original strings (as x and y) are reconstructed and printed to the user.
I know this has been a lot. Read it a few times, and let it sink in. I hope in the end you get closer to understanding what the code is supposed to do.