An O(n) time algorithm to find the longest palindromic substring

longest_palindromic_substring

/* 
 * File:   main.cpp
 * Author: abinashmeher999
 *
 * Created on 16 November, 2014, 2:13 PM
 */

#include <iostream>
#include <string>
#include <cmath>
#include <new>
#include <algorithm>

using namespace std;

/*This algorithm uses just O(n) extra space only
  that too only one more integer array of length n.
  With this algorithm we need to traverse the array only twice,
  if we exclude the one needed to initialize all to 1.
  So both time and space complexity wise, this seems good.*/
int longestpalsubstr(string A) {
    //there are no nested 2 'for' loops in this function (except in printing the max substring but that too can be done in O(n))
    int n = A.size();
    int *Y = new int[n];
    int temp = 1, max;
    char t;

    //initializes the array
    for (int i = 0; i < n; i++) {
        Y[i] = 1;
    }

    //print the given string
    cout << "S = " << A << endl;

    //calculates the length of same character substring after the alphabet including itself
    //like for a,b,a, b,b,b, a, b,b,b, a,b,a
    //         1,1,1, 3,2,1, 1, 3,2,1, 1,1,1
    for (int m = n - 1; m > 0; --m) {
        t = A.at(m);
        Y[m] = temp; //which is equal to 1 initially
        if (m - 1 < 0) break;
        if (A.at(m - 1) == A.at(m)) {
            ++temp;
            continue;
        } else {
            temp = 1;
        }
    }
    if (A.at(0) == A.at(1)) {
        Y[0] = Y[1] + 1;
    }

    //prints Y
    cout << "Y = ";
    for (int m = 0; m < n; m++) {
        cout << Y[m] << "";
    }
    cout << endl;

    //finds the maximum palindrome length that starts with the character at index k
    for (int k = n - 2; k > 0; k--) {               //traverses the array from the end
        if (k + Y[k] < n) {                         //checks if the index to be accessed is within n-1
            if (A.at(k - 1) == A.at(k + Y[k])) {    //checks if, preceeding char == char at index(k+Y[k])
                Y[k - 1] = Y[k] + 2;                //if yes increases Y[k-1] by 2
            }
        }
    }
    //there are exceptions, but it doesn't compromise with the final answer
    //         0  1 2 3 4 5 6 7 8 9 10
    //like S = a ,c,c,c,a,c,a,c,c,c,a
    //     Y = 11,9,7,5,3,1,5,3,1,1,1
    //in this case for c in middle (index 5) it is 1 (when Y by common sense should contain 3)
    //but we still get the correct answer, so we cant say that for all cases
    //Y contains the length of the largest palindrome starting from that index

    //prints Y
    cout << "After finding longest palindromic substring\nY = ";
    for (int m = 0; m < n; m++) {
        cout << Y[m] << ",";
    }
    cout << endl;

    //finds maximum in Y
    max = *max_element(Y, Y + n);

    //for printing purposes only
    cout << "Part II: Length = " << max << ". Substrings: ";
    for (int i = 0; i < n; i++) {
        if (Y[i] == max) {
            for (int j = 0; j < max; j++) {
                cout << A.at(i + j);
            }
            cout << " ";
        }
    }
    cout << "\n";

    return max;
}

int main() {
    int max;
    string A;
    cout << "Enter the string" << endl;
    cin >> A;
    max = longestpalsubstr(A);
    return 0;
}