Using manacher algorithm. C++ solution.


  • 2
    E
    class Solution {
    public:
    string longestPalindrome(string s) 
    {
        return manacher(s);
    }
    private:
    string manacher(string s)
    {
    	string str(s.length() * 2 + 1, '#');
    	int k = 0;
    	for (int i = 0; i < s.length(); ++i)
    	{
    		str[k++] = '#';
    		str[k++] = s[i];
    	}
    	str[k] = '#';
    
    	int n = str.length();
    	int mostRight = 0;
    	int mostRightIdx = 0;
    	int *p = new int[n];
    
    	for (int i = 0; i < n; ++i)
    	{
    		if (mostRight > i)
    			p[i] = min(p[2 * mostRightIdx - i], mostRight - i);
    		else
    			p[i] = 1;
    
    		while (i - p[i] >= 0 && i + p[i] < n && str[i - p[i]] == str[i + p[i]])
    			p[i]++;
    
    		if (i + p[i] > mostRight)
    		{
    			mostRight = i + p[i];
    			mostRightIdx = i;
    		}
    	}
    
    	int maxRadis = 0;
    	int maxRadisIdx = 0;
    	for (int i = 0; i < n; ++i)
    	{
    		if (maxRadis < p[i])
    		{
    			maxRadis = p[i];
    			maxRadisIdx = i;
    		}
    	}
    
        int len = 0;
        if (maxRadis % 2 == 0)
            len = maxRadis - 1;
        else
            len = maxRadis / 2 * 2;
        
        string ans(len, ' ');
        k = 0;
        for (int i = maxRadisIdx - maxRadis + 1, cnt = 0; cnt < maxRadis; i += 2, cnt++)
            ans[k++] = str[i + 1];
            
    	return ans;
    }
    };

  • 0
    E

    Don't look at my code at first, just Google about "manacher algorithm", when you understand the algorithm then look back to my code.


  • 0
    S

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

    void input(char a[],int sza)
    {
    for(int i=0;i<sza;i++)
    {
    cin>>a[i];
    }

    }

    void print(char a[],int start, int b)
    {
    for(int j=start;j<=b;j++)
    {
    cout<<a[j];
    }

    }

    void func(char a[],int sza)
    {
    int high,low,start,maxlength=1; //maxlength is the answer i.e. length of longest palindrome in substring
    for(int i=1;i<sza;i++)
    {
    //the follwoing code is for even length palindrome with i-1 and i as center;
    low=i-1;
    high=i;

    while(low>=0 && high<sza && a[low]==a[high])
    {
    if((high-low+1)>maxlength)
    {
    start=low;
    maxlength=high-low+1;
    }
    low--;
    high++;

    }

    // the following code is for odd length palindrome with i as center
    low=i-1;
    high=i+1;
    while(low>=0 && high<sza && a[low]==a[high])
    {
        if((high-low+1)>maxlength)
        {
            start=low;
            maxlength=high-low+1;
        }
        low--;
        high++;
    }
    

    }

    cout<<endl<<"printing the substring palindrome : "<<endl;
    print(a,start,start+maxlength-1);

    }

    int main()
    {
    char a[15],b[15];
    int sza; //sza is size of d array
    cout<<endl<<"enter d size of array or string"<<endl;
    cin>>sza;
    input(a,sza);
    func(a,sza);
    return 0;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.