// zuichanghuiwen2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
int c[20][20];
void LPS(string str)
{
	int m = str.length();
	int j;
	for (int j = 0; j < m; j++)
		for (int i = j + 1; i < m; i++)
			c[i][j] = 0;
	for (int i = 0; i < m; i++)
		c[i][i] = 1;
	for(int l=2;l<=m;l++)       //这里一定要按长度从短开始算
		for (int i = 0; i<m-l+1; i++)
		{
			j = i + l - 1;
			if (str[i] == str[j])
				c[i][j] = c[i + 1][j - 1] + 2;
			else
				c[i][j] = c[i + 1][j] > c[i][j - 1] ? c[i + 1][j] : c[i][j - 1];
		}
}


void rebuild(string str)
{
	int m = c[0][str.length() - 1];
	int mi;
	for (auto i = 0; i < str.length(); i++)
		if (str[i] == str[i + m - 1]) {
			mi = i;
			break;
		}
	for (int i = mi; i < mi + m; i++)
		cout << str[i];
}

int main()
{
	string str("dgdfgdfabcacbagfgfg");
	LPS(str);
	rebuild(str);
	while (1);
    return 0;
}