(Method 2)Minimum characters to be added at front to make string palindrome

//Method 2
// Efficient approach: We can solve this problem efficiently in O(n) time using lps array of KMP algorithm.
// First we concat string by concatenating given string, a special character and reverse of given string 
// then we will get lps array for this concatenated string, 
// recall that each index of lps array represent longest proper prefix which is also suffix. 
// We can use this lps array for solving the problem. 
// For string = AACECAAAA
// Concatenated String = A  A  C  E  C  A  A  A  A  $  A  A  A  A  C  E  C  A  A
// LPS array will be    {0, 1, 0, 0, 0, 1, 2, 2, 2, 0, 1, 2, 2, 2, 3, 4, 5, 6, 7}

#include <bits/stdc++.h>
using namespace std;

vector<int> computeLPSArray(string str)
{
	int M = str.length();
	vector<int> lps(M);

	int len = 0;
	lps[0] = 0; // lps[0] is always 0
	int i = 1;
	while (i < M)
	{
		if (str[i] == str[len])
		{
			len++;
			lps[i] = len;
			i++;
		}
		else // (str[i] != str[len])
		{
			if (len != 0)
			{
				len = lps[len-1];
			}
			else // if (len == 0)
			{
				lps[i] = 0;
				i++;
			}
		}
	}
	return lps;
}

int getMinCharToAddedToMakeStringPalin(string str)
{
	string revStr = str;
	reverse(revStr.begin(), revStr.end());
	string concat = str + "$" + revStr;
	vector<int> lps = computeLPSArray(concat);
	return (str.length() - lps.back());
}

int main()
{
	string str = "AACECAAAA";
	cout << getMinCharToAddedToMakeStringPalin(str);
	return 0;
}