5. 最长回文子串

佚名 7年前 (2019-04-24) 随笔 1394人围观抢沙发百度已收录

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<vector>
#include <algorithm>
#include <functional>
#include<string>
#include<fstream>
#include <sstream>
#include <assert.h>
using namespace std;
class Solution {
public:
	string longestPalindrome(string s)
	{
		if (s.length() < 0) return "";//如果长度小于0则返回空
		int n = s.size();//获得字符串的长度
		vector<vector<bool>> dp(n, vector<bool>(n, false));//定义bool向量
		int maxlen = 1, start = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j <= i; j++)
			{
				if (i - j < 2) dp[i][j] = (s[i] == s[j]);
				else
					dp[i][j] = (s[i] == s[j] && dp[i - 1][j + 1] == 1);
				if (dp[i][j] && maxlen < i - j + 1)
				{
					maxlen = i - j + 1;
					start = j;
				}
			}
		}
		return s.substr(start, maxlen);
	}

};

string stringToString(string input) {
	assert(input.length() >= 2);
	string result;
	for (int i = 1; i < input.length() - 1; i++) {
		char currentChar = input[i];
		if (input[i] == '\\') {
			char nextChar = input[i + 1];
			switch (nextChar) {
			case '\"': result.push_back('\"'); break;
			case '/': result.push_back('/'); break;
			case '\\': result.push_back('\\'); break;
			case 'b': result.push_back('\b'); break;
			case 'f': result.push_back('\f'); break;
			case 'r': result.push_back('\r'); break;
			case 'n': result.push_back('\n'); break;
			case 't': result.push_back('\t'); break;
			default: break;
			}
			i++;
		}
		else {
			result.push_back(currentChar);
		}
	}
	return result;
}

int main() {
	string line;
	while (getline(cin, line)) {
		string s = stringToString(line);

		string ret = Solution().longestPalindrome(s);

		string out = (ret);
		cout << out << endl;
	}
	return 0;
}