C++ using KMP , very easy logic


#1

#define ll long long
int preKMP(string pattern )
{
ll m = pattern.length(), k;ll f[m]={0};
f[0] = -1;
for (ll i = 1; i < m; i++)
{
k = f[i - 1];
while (k >= 0)
{
if (pattern[k] == pattern[i - 1])
break;
else
k = f[k];
}
f[i] = k + 1;
}
return f[m-1];
}
int Solution::solve(string A)
{
string b=A;
reverse(b.begin(),b.end());
b=b+’*’+A;
return A.size()-preKMP(b)-1;
}