Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 动态数组（另附递归）

Posted by AboKand at 2020-04-10 17:37:52 on Problem 1458
```使用动态数组，每次都重新分配内存

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

//int findSame(string a, string b)
//{
//	if (a == "" || b == "") return 0;
//	if (a[0] == b[0])
//	{
//		return 1 + findSame(a.substr(1), b.substr(1));
//	}
//	return max(findSame(a.substr(1), b), findSame(a, b.substr(1)));
//}

//开始用递归但一直超时，改为数组

int main()
{
string x, y;
int** result, size_x, size_y, i, j;
while (cin >> x >> y)
{
size_x = x.size(); size_y = y.size();
result = new int* [size_x + 1];
for (i = 0; i <= size_x; i++)
{
result[i] = new int[size_y + 1];
result[i][0] = 0;
}
for (j = 0; j <= size_y; j++) result[0][j] = 0;
//result[i][j]代表考虑到x前i个，y前j个，的最大公共子串
//第0行和第0列无实际意义，方便迭代，均设为0

for (i = 1; i <= size_x; i++)
{
for (j = 1; j <= size_y; j++)
{
if (x[i - 1] == y[j - 1]) result[i][j] = result[i - 1][j - 1] + 1;
else result[i][j] = max(result[i - 1][j], result[i][j - 1]);
}
}
cout << result[size_x][size_y] << endl;
for (i = 0; i <= size_x; i++) delete[]result[i];
delete[] result;
}

return 0;
}```

Followed by: