最长回文字符串

野性酷女 2022-08-01 20:58 197阅读 0赞

在一个字符串中，找出最长的回文字符串

// MaxSameReverse.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<deque>
    #include<iostream>
    using namespace std;
    
    
    bool IsReverseTheSame(deque<char>in);
    deque<char> substring(deque<char> input,int beg,int end);
    bool MaxSameReverse(deque<char>input);
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	deque<char>cc;
    	cc.push_back('g');
    	cc.push_back('a');
    	cc.push_back('b');
    	cc.push_back('c');
    	cc.push_back('b');
    	cc.push_back('a');
    	if (IsReverseTheSame(cc))//测试IsReverseTheSame函数
    		cout << 1 << endl;
    	else
    		cout << 0 << endl;
    	cc.push_back('c');
    	cout << cc[2] << endl;
    
    	MaxSameReverse(cc);
    	
    	system("pause");
    	return 0;
    }
    
    bool IsReverseTheSame(deque<char>in)
    {
    	while (in.size() > 2)
    	{
    		if (in.front() != in.back())
    		{
    			return false;
    		}
    		in.pop_back();
    		in.pop_front();
    		IsReverseTheSame(in);
    	}
    	if (in.size() == 2)
    	{
    		if (in[0] == in[1])
    			return true;
    		return false;
    	}
    	if (in.size() == 1)
    		return true;
    }
    
    deque<char> substring(deque<char> input, int beg, int end)
    {
    	deque<char>out;
    	for (int i = beg; i < end + 1; i++)
    		out.push_back(input[i]);
    	return out;
    }
    
    
    bool MaxSameReverse(deque<char>input)
    {
    	bool flag = false;
    	for (int i = input.size(); i >0; i--)
    	{
    		for (int k = 0; k < input.size() - i+1; k++)
    		{
    			deque<char>ww(substring(input, k, i+k - 1));
    			
    			if (IsReverseTheSame(ww))
    			{
    				flag = true;
    				for (int m = 0; m < ww.size(); m++)
    					cout << ww[m];
    				cout << endl;
    			}
    			if (flag)
    				break;
    		}
    		if (flag)
    			break;
    	}
    	return flag;
    }
    
    //开始用char*做递归，陷入死循环，后来改用deque
    
    /*
    bool IsReverseTheSame(char* in)
    {
    	while (strlen(in)> 2)
    	{
    		if (in[0] != in[strlen(in) - 1])
    		{
    			return false;
    		}
    		char*out = new char[strlen(in) - 2];
    		out = substring(in);
    		
    		cout << out << endl;
    		int pp = strlen(out);
    		cout << pp<<endl;
    		IsReverseTheSame(out);
    		
    	}
    	if (strlen(in) == 2)
    	{
    		if (in[0] == in[1])
    			return true;
    		return false;
    	}
    	if (strlen(in) == 1)
    		return true;
    
    }
    
    */