2021.9.10學習記錄(基本算法)對稱子字元串的最大長度（習題）

對稱子字元串的最大長度

輸入一個字元串，輸出該字元串中對稱的子字元串的最大長度。比如輸入字元串“google”，由于該字元串裡最長的對稱子字元串是“goog”，是以輸出4。

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;


//char s[] = "google";

//判斷一個字元串是否是對稱的
bool IsSymmetricalString(char* pstart ,char* pend)
{
	//兩個指針不能為空
	//頭指針不能大于尾指針
	if (pstart == NULL || pend == NULL || pstart > pend)
		return false;

	//頭指針小于尾指針時判斷兩位指針的值是否相等
	while (pstart < pend)
	{
		if (*pstart != *pend)
			return false;
		else
		{
			//頭指針指向下一個,類似于s[0++]
			pstart++;
			//尾指針指向上一個,類似于s[len--]
			pend--;
		}
	}
	return true;

}


//求最大對稱子串的長度
//從内向外比較
//時間複雜度O(n²)
int MaxStrIntoOut(char* pstring)
{
	int maxlength = 1;

	char* pchar = pstring + 1;//pchar=pstring位址-1的位置
	while (*pchar != '\0')
	{
		char* pfirst = pchar - 1;//pchar位址-1的位置
		char* psecond = pchar + 1;//pchar位址+1的位置

		//
		while (pfirst > pstring && psecond < &pstring[strlen(pstring) - 1] && *pfirst == *psecond)
		{
			pfirst--;
			psecond++;
		}

		int templen = psecond - pfirst + 1;
		if (templen > maxlength)
			maxlength = templen;


		pfirst = pchar - 1;
		psecond = pchar;
		
		while (pfirst > pstring && psecond < &pstring[strlen(pstring) - 1] && *pfirst == *psecond)
		{
			pfirst--;
			psecond++;
		}

		templen = psecond - pfirst + 1;
		if (templen > maxlength)
		{
			maxlength = templen;
		}
		pchar++;
	}
	return maxlength;
}


//從頭周遊字元串
//時間複雜度O(n³)
int MaxStrOnetoEnd(char* pstring)
{
	if (pstring == NULL)
		return 0;

	int maxlen = 1;

	int len = strlen(pstring);
	char* pfirst = pstring;
	while (pfirst < &pstring[len - 1])
	{
		char* psecond = pfirst + 1;
		while (psecond <= &pstring[len - 1])
		{
			if (IsSymmetricalString(pfirst, psecond))
			{
				int templen = psecond - pfirst + 1;
				if (templen > maxlen)
				{
					maxlen = templen;
				}
			}
			psecond++;
		}
		pfirst++;
	}
	return maxlen;

}

void main()
{
	cout << "請輸入字元串！" << endl;
	char* s = new char[1000];
	cin >> s;

	cout << "對稱字元串的最大長度是:" << endl;
	cout << MaxStrOnetoEnd(s) << endl;

	delete[] s;
}