// CPP program for above approach
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
// This class builds the dfa and
// precomputes the state.
// See KMP algorithm for explanation
class kmp_numeric {
private:
int n;
int** dfa;
public:
kmp_numeric(string& s)
{
n = s.length();
int c = 256;
// Create dfa
dfa = new int*[n];
// Iterate from 0 to n
for (int i = 0; i < n; i++)
dfa[i] = new int;
int x = 0;
// Iterate from 0 to n
for (int i = 0; i < c; i++)
dfa[0][i] = 0;
// Initialise dfa[0][s[0]] = 1
dfa[0][s[0]] = 1;
// Iterate i from 1 to n-1
for (int i = 1; i < n; i++) {
// Iterate j from 0 to c - 1
for (int j = 0; j < c; j++) {
dfa[i][j] = dfa[x][j];
}
dfa[i][s[i]] = i + 1;
x = dfa[x][s[i]];
}
}
// This function finds the overlap
// between two strings,by
// changing the state.
int longest_overlap(string& query)
{
// q1 is length of query
int ql = query.length();
int state = 0;
// Iterate from 0 to q1 - 1
for (int i = 0; i < ql; i++) {
state = dfa[state][query[i]];
}
return state;
}
};
int min_appends(string& s)
{
// Reverse the string.
reverse(s.begin(), s.end());
// Build the DFA for the
// reversed String
kmp_numeric kmp = s;
// Get the original string back
reverse(s.begin(), s.end());
// Largest overlap in this case is the
// largest string from the end which
// is a palindrome.
int ans = s.length() - kmp.longest_overlap(s);
return ans;
}
// Driver Code
int main()
{
string s = "deep";
// Answer : 3
string t = "sososososos";
// Answer : 0
cout << min_appends(s) << endl;
cout << min_appends(t) << endl;
}
