Palindrome seeker

[oggy22]

Write the algorithm to search for palindromes with multiple words.

The grammar should be relaxed/ignored, or palindromes with more grammatical sense should be scored higher.

Focus on Serbian language.

The input to the algorithm:

• list of words (non-nominal words) including all the word forms
• the max palindrome length

The algorithm:

• Make a trie out of the list of words
• Make a trie out of the list of inverted words (e.g. abc -> cba)
• Recursively walk both tries such that the same char is taken
  • if both tries are at wordEnd=bool nodes, an even count palindrome with two halves is found
  • if you can walk the prefix of one trie into another, an even count palindrome is found with center in midword
  • right before the recursive call, check if the char being advanced is the same letter in the word. If yes, a palindrome is found with center in midword
• At the end perform grammar analysis on each palindrome and sort them by grammar compliance. Grammar compliance can be defined as number of grammar nodes found.

class trie_node
{
  bool wordEnd;
  map<char, trie_node*> children;
}