Number of palindromes in question 5 of C language deduction (two methods)

Give you a string s, find s The longest palindrome substring in .

Example 1：

Input ：s = "babad"
Output ："bab"
explain ："aba" It's the same answer .

Example 2：

Input ：s = "cbbd"
Output ："bb"

source ： Power button （LeetCode）
link ：https ://leetcode.cn/problems/longest-palindromic-substring
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

  Method 1 ： Create a new string array , Reverse the original string array , Traversing two arrays at the same time , Find the common substring of two string arrays , And return the largest substring , The time complexity is O(n^2), Spatial complexity O(n)
  Method 2 ： Central diffusion method , The time complexity is O(n^2), The space complexity is O(1)
We observe that the two sides of the palindrome center mirror each other . therefore , Palindrome can be expanded from its center , And only 2n - 1 Such a center .
You may ask , Why would it be 2n - 1 individual , instead of n Center ？
Because the center of palindrome should distinguish between single and double .
If the center of the palindrome is dual , for example abba, Then it can be divided into ab bb ba, about n Length string , Such a division has n - 1 Kind of .
The center of the false palindrome is singular , for example abcd, Then it can be divided into a b c d, about n Length string , Such a division has n Kind of .
about n Length string , In fact, we don't know whether the center of its palindrome string is singular or even , So we're going to traverse both cases , That is to say n + (n - 1) = 2n - 1, So the time complexity is O(n).
When the center is determined , We need to expand palindromes around this center , Then the longest palindrome may be the whole string , So the time complexity is O(n^2).
So the total time complexity is O(n^2),

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


char * test1(char * s) 
{
	char s1[100] = "";
	char s2[100] = "";
	int i = 0;
	int j = 0;
	int p = 0, p1 = 0,p2 = 0 ,p3 = 0;
	int max = 0;
	for (i = 0; i < strlen(s); i++)
		s1[strlen(s) - i - 1] = s[i];
	//printf("%s\n", s1);

	for (i = 0; i < strlen(s); i++)
	{	
		while (j<=strlen(s))
		{
			if (s[i] != s1[j]||s1[j]=='\0')
			{
				j++;
				if (p > max)
				{
					max = p;
					for (p1 = j - 1 - p; p1 < j - 1; p1++)
					{
						s2[p2] = s1[p1];
						p2++;
					}
				}
				p = 0;
				p2 = 0;
			}
			else if (s[i] == s1[j]&&s1[j]!='/0')
			{
				i++;
				j++;
				p++;
			}
		}
		j = 0;
		p3++;
		i = p3;
	}
	return s2;
}

char * test2(char * s) 
{
	int i, j, k;
	int slen;
	int len = 0;
	int maxlen = 0;
	char *sout;

	if (s == NULL) return NULL;

	// The border 
	slen = strlen(s);
	if (slen == 1) return s;
	if (slen == 2) {
		if (s[1] != s[0]) s[1] = '\0';
		return s;
	}
	if (slen == 3 && s[1] == s[0] && s[1] != s[2]) {
		s[2] = '\0';
		return s;
	}

	sout = (char*)malloc(slen + 1);
	memset(sout, '\0', slen + 1);
	sout[0] = s[0];

	i = j = k = 1;
	while (i < slen) {
		// Situation 1 , similar abcddcba
		if (s[i + 1] == s[i]) {
			len = 2;
			j = i - 1;
			k = i + 2;
			while (j >= 0 && k < slen) {
				if (s[j] == s[k]) {
					len += 2;
					j--;
					k++;
				}
				else {
					j++;
					k--;
					break;
				}
			}
		}
		if (k == slen) j++;
		if (j < 0) j = 0;
		if (len > maxlen) {
			memcpy(sout, s + j, len);
			maxlen = len;
			len = 0;
		}
		// situation 2, similar ABCDCBA
		if (s[i - 1] == s[i + 1]) {
			len = 1;
			j = i - 1;
			k = i + 1;
			while (j >= 0 && k < slen) {
				if (s[j] == s[k]) {
					len += 2;
					j--;
					k++;
				}
				else {
					j++;
					k--;
					break;
				}
			}
		}
		if (k == slen) j++;
		if (j < 0) j = 0;
		if (len > maxlen) {
			memcpy(sout, s + j, len);
			maxlen = len;
			len = 0;
		}
		i++;
	}
	return sout;
}



int main()
{
	char s[100] = "aaaaaa";
	char s2[100] = "";
	//strcpy(s2,test1(s));
	strcpy(s2, test1(s));
	printf("%s", s2);
	return 0;
}