[CS Academy] Palindromic Friendship

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Palindromic Friendship
Source            : CS Academy
Category          : String
Algorithm         : Manacher Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 3e5 + 5;  
  
vector <int> relation[maxn];  
  
bool can(int x, int y)  
{  
      return find(relation[x].begin(), relation[x].end(), y) != relation[x].end();  
}  
  
int manacher(vector <int> &s)  
{  
      int n = s.size();  
      vector < vector <int> > p(2, vector <int> (n, 0));  
  
      for (int z = 0, l = 0, r = 0; z < 2; z++, l = 0, r = 0)  
      {  
            for (int i = 0; i < n; i++)  
            {  
                  if (i < r) p[z][i] = min(r - i + !z, p[z][l + r - i + !z]);  
                  int L = i - p[z][i];  
                  int R = i + p[z][i] - !z;  
                  while (L - 1 >= 0 && R + 1 < n && can(s[L - 1], s[R + 1])) p[z][i]++, L--, R++;  
                  if (R > r) l = L, r = R;  
            }  
      }  
      int maxi = *max_element(p[0].begin(), p[0].end()) * 2;  
      maxi = max(maxi, *max_element(p[1].begin(), p[1].end()) * 2 + 1);  
      return maxi;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(3);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, m;  
      cin >> n >> m;  
      for (int i = 1; i <= m; i++)  
      {  
            int x, y;  
            cin >> x >> y;  
            relation[x].push_back(y);  
            relation[y].push_back(x);  
      }  
      vector <int> arr;  
      for (int i = 1; i <= n; i++)  
      {  
            sort(relation[i].begin(), relation[i].end());  
            arr.push_back(i);  
      }  
      cout << manacher(arr) << '\n';  
  
}