Nice solution :) Using unordered_map it should become clearly O(m)

Because b ≤ 10⁸

Also wondering

I tried to enumerate every pair of vertices (B, D) and calculate the number of diamonds (assuming these two are the middle vertices of a diamond). Intersecting their parents and their children, I obtained the number of possible vertices (A, C) that could form a diamond. Also intersecting these two sets, I obtained the number of "repeated" vertices that are both parents and children of A and B, and thus can't form a diamond with itself. And add to the answer the value (parents * children — their intersection).

But this approach gave TLE

Take a look at Timus online judge. You can filter the problems by DP tag and sort them by difficulty — link
Have fun :)

Suppose that we have solved the first part by constructing the DP table for LCS. Now we can backtrack to obtain indices of common characters for both strings that form this LCS.
Let's define them as {a₁, a₂, ..., a_k} for the first string A, and {b₁, b₂, ..., b_k} for the second string B.
Of course, all unique shortest strings will contain these common characters, and the rest of A and B between these characters could be shuffled in all possible ways mantaining the relative order.

For example, consider the case LAILI and MAJNU where a₁ = b₁ = 2 (the A character).
Before these indices there are only L and M letters which can be ordered as LM or ML (2 combinations in total).
Next char will be A, and the rest (ILI and JNU) can be ordered in many ways such as ILIJNU, ILJNUI, ILJNIU etc.
There are 20 such combinations in total. We multiply all combinations together and obtain the answer 40.

Thus, we should calculate the number of shuffles for every substring between common LCS characters (a_i... a_i + 1) and (b_i... b_i + 1) — let's call them s_i and t_i — and multiply the results.
For calculating the number of shuffles we possibly can iterate through all of them using recursion since the problem statement says total number won't exceed 263.

But in fact, if we look deeper it's exactly the number of compositions of |s_i| as (|t_i| + 1) non-negative integer terms. You can write it down and see by yourself. The direct formula is and is explained here.

Could you please explain how we can fix one point if all of them probably were shuffled?

I had an idea to calculate all pairwise distances for some fixed permutation (there are 28 segments in total) and sort them. Now, if first 12 of them are equal, next 12 are equal and last 4 are equal, it's a cube. But I didn't have time to code this solution and can't prove it

If this question is still open, a solution based on Aho-Corasic + DP is explained here — http://www.cprogramdevelop.com/2578501/ (there are also links to other related solutions on the same page)

Are nonexistent infinity elements placed to the right/bottom edge of the tableau (since rows and columns are sorted); or they could appear anywhere in the matrix?

Here's the code how this could be done using recursion with caching. But, you can't do it faster than the number of all possible combinations:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<string> > cache;
string s;
int n;

void subseq(int to)
{
	string tmp = "";
	for (int i = to - 1; i >= 0; i--)
	{
		if (cache[i].size() == 0)
			subseq(i);

		for (int j = 0; j < cache[i].size(); j++)
		{
			tmp = cache[i][j] + s[to - 1];
			cache[to].push_back(tmp);

			cout << tmp << endl;
		}
	}
}

int main()
{
	cin >> s;
	n = s.length();

	for (int i = 0; i <= n; i++)
		cache.push_back(vector<string>());
	cache[0].push_back("");

	subseq(n);

	return 0;
}

Thank you for the link. Haven't found it, very interesting