# CHEFSHIP Using Prefix Function

Can someone please explain the approach to this problem using prefix function? Why editorial solution contains two lps array?
Question: CHEFSHIP Problem - CodeChef
Soluttion:

``````#include <bits/stdc++.h>

using namespace std;

// char input[] = "input/input00.txt";
// char output[] = "output.txt";

const int N = 200010;

int a[N],lps1[2][N],lps2[2][N];
string s;

void computeLPSArray1(int key)
{
int len = 0;
lps1[key][0] = 0;
int i = 1;

while(i < s.size())
{
if(s[i] == s[len])
{
len++;
lps1[key][i] = len;
i++;
}
else
{
if(len != 0)
len = lps1[key][len - 1];
else
{
lps1[key][i] = 0;
i++;
}
}
}
}

void computeLPSArray2(int key)
{
int len = 0;
lps2[key][0] = 0;
int i = 1;

while(i < s.size())
{
if(s[i] == s[len])
{
len++;

if(2*len > i+1)
len = lps1[key][len - 1];

lps2[key][i] = len;
i++;
}
else
{
if(len != 0)
len = lps1[key][len - 1];
else
{
lps2[key][i] = 0;
i++;
}
}
}
}

int main()
{
// freopen(input, "r", stdin);
// freopen(output, "w", stdout);

int t;
cin >> t;

while(t--)
{
cin >> s;

int n = s.size();

for(int i=0;i<n;i++)
lps1[0][i] = lps1[1][i] = lps2[0][i] = lps2[1][i] = 0;

computeLPSArray1(0);
computeLPSArray2(0);
reverse(s.begin(),s.end());
computeLPSArray1(1);
computeLPSArray2(1);

int ans = 0;

for(int i=1;i<n-2;i+=2)
{
if((2*lps2[0][i] == (i+1)) && (2*lps2[1][n-i-2] == (n-i-1)))
ans++;
}

cout << ans << endl;
}

return 0;
}
``````