This is a problem from Codeforces Round 975. I tried to solve it in the round time and expected to get higher rating. A solution of binary search to this problem jumped out in my mind, and I coded it quickly, but I got WA again and again. Please help me, maybe there are some mathematical wrong int my solution or some bugs in my codes, please pointed it out, thank you!!!!!

Problem_Link

My_Submission

The request of the problem is printing out the LCS of two strings. Then I submitted my solution to AtCoder, the result returned from OJ was RE or TLE. Ensuring that there is no boundary violations occurred and time complexity is O(lens1 * lens2), I can't find out where is wrong..... Help me plz.

string dp[3010][3010];

void solve()
{
	string s1, s2; cin >> s1 >> s2;
	s1 = ' ' + s1;	s2 = ' ' + s2;

	int lens1 = s1.length() - 1, lens2 = s2. length() - 1;
	for(int i = 1; i <= lens1; i++)
	{
		for(int j = 1; j <= lens2; j++)
		{
			if(s1[i] == s2[j])
				dp[i][j] = dp[i - 1][j - 1] + s1[i];
			else
			{
				if(dp[i - 1][j].length() > dp[i][j - 1].length())
					dp[i][j] = dp[i - 1][j];
				else dp[i][j] = dp[i][j - 1];
			}
		}
	}

	cout << dp[lens1][lens2] << endl;
}	

Problem Link

My Submission

Problem_Link

My_Submission_Link

Thanks!!!!!

Can someone tell me why there is a '*' before someone 's name. What that means????