- // zuichanghuiwen.cpp : 定义控制台应用程序的入口点。
- //
- #include "stdafx.h"
- #include<iostream>
- #include<string>
- #include<stack>
- using namespace std;
- void palindrome(string str)
- {
- stack<char> sta; //翻转字符串
- for (int i = 1; i < str.length(); i++)
- sta.push(str[i]);
- string str2(str.length(),"/0");
- for (int i = 1; i < str.length(); i++)
- {
- str2[i] = sta.top();
- sta.pop();
- }
- int m = str.length()-1; //求愿字符串与翻转字符串的最长公共子序列
- int n = str2.length()-1;
- int c[20][20];
- for (int i = 1; i <= m; i++)
- c[i][0] = 0;
- for (int j = 0; j <= n; j++)
- c[0][j] = 0;
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- if (str[i] == str2[j]) {
- c[i][j] = c[i - 1][j - 1]+1;
- }
- else
- c[i][j] = 0;
- int max = 0, maxi = 0,maxj=0; //重建最大子序列
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- if (c[i][j] > max) {
- max = c[i][j];
- maxi = i;
- maxj = j;
- }
- for (int i = maxi; i >= maxi - max + 1; i--)
- cout << str2[i];
- }
- int main()
- {
- string str("asddsa");
- palindrome(str);
- while (1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1999771.html