Dat je niz reči (w_i) dužine n. Uz pomoć ovih reči moguće je kreirati n² parova (w_i, w_j) reči, čijom konkatenacijom dobijamo reč w_ij. Napisati program koji ispituje koliko ima parova čijom konkatenacijom dobijamo palindrom. Reč s je palindrom ukoliko se čita isto i sa leve i sa desne strane (npr aabaa, a, abcba).

Ulaz:

(Ulazni podaci se učitavaju iz datoteke palap.in.) U prvom redu ulaza nalazi se prirodan broj n (n ≤ 5.000) koji označava broj reči. Svaki od narednih n redova sadrži po jednu reč. Reči su sastavljene od malih slova engleskog alfabeta i njihova dužina ne prelazi 500.

Izlaz:

(Izlazni podaci se ispisuju u datoteku palap.out.) U prvom i jedinom redu izlaza ispisati broj parova čijom se konkatenacijom dobija palindrom.

Primer 1.

3
a
aa
ab

5

Objašnjenje.

Parovi koji kreiraju palindrome su (1, 1), (1, 2), (2, 1), (2, 2) i (3, 1).

#include<stdio.h>
#include<string.h>
#include<time.h>
#define MAX_N 5001
#define MAX_LEN 501

int n, sol, currentIndexChild, h [MAX_LEN * 2], len [MAX_N];
int childStartIndex [MAX_N * MAX_LEN * 26], numPal [MAX_N * MAX_LEN * 26];
char words [MAX_N][MAX_LEN], pattern [MAX_LEN], text [MAX_LEN * 2];
bool palSufix [MAX_LEN];

  void input()
  {
    FILE *in = fopen("palap.in", "r");
    fscanf (in, "%d", &n);
    for (int i = 0; i < n; i++)
    {
      fscanf (in, "%s", & words [i]);
      len [i] = strlen(words [i]);
    }
    fclose(in);
  }

  void output()
  {
    FILE *out = fopen("palap.out", "w");
    //printf ("%d\n", sol);
    fprintf(out, "%d\n", sol);
    fclose(out);
  }

  int min (int a, int b)
  {
    return (a < b) ? a : b;
  }

  void _initPalSufix(int k)
  {
    int m = len [k];
    for (int t = 0; t < m; t++)
    {
      text [t] = words [k][t];
      pattern [t] = words [k][m - 1 - t];
    }
    for (int t = 0; t < m; t++)
      text [m + t] = '#';

    h [0] = -1;
    int i = 0, j = -1;
    while (i < m)
    {
      while (j >= 0 && (pattern [i] != pattern [j]))
        j = h [j];
      i++;
      j++;
      h [i] = j;
    }

    int maxSufPal = 0;
    i = 1, j = 0;
    while (i < 2 * m)
    {
      while (j >= 0 && text[i] != pattern[j])
        j = h[j];
      i++; j++;
      if (i == m)
        if (j > maxSufPal)
          maxSufPal = j;
    }

    for (i = 0; i < m; i++)
      palSufix [i] = false;
    while (maxSufPal >= 0)
    {
      palSufix [m - maxSufPal] = true;
      maxSufPal = h [maxSufPal];
    }

    palSufix [0] = true;
    for (int i = 0; i < m; i++)
      if (pattern [i] != pattern [m - 1 - i])
      {
        palSufix [0] = false;
        break;
      }
  }

  void addWordInTrie(int index, char word [], bool emptyIsPal)
  {
    int nodeIndex = 0, charIndex = 0;
    int m = len [index];
    while (charIndex < m)
    {
      if (palSufix [charIndex])
        numPal [nodeIndex] += 1;

      if (childStartIndex [nodeIndex] == -1)
      {
        childStartIndex [nodeIndex] = currentIndexChild;
        currentIndexChild += 26;
      }
      
      nodeIndex = childStartIndex [nodeIndex] + (word [charIndex] - 'a');
      charIndex++;
    }
    if (emptyIsPal)
      numPal [nodeIndex] += 1;
  }

  void visitWord (char word [], int wIndex)
  {
    int nodeIndex = 0;
    int m = len [wIndex];
    int index = m - 1;
    while (index >= 0)
    {
      if (childStartIndex [nodeIndex] != -1)
        nodeIndex = childStartIndex [nodeIndex] + (word [index] - 'a');
      else
        break;
      index--;
    }
    if (index == -1)
      sol += numPal [nodeIndex];
  }

  void r(int index)
  {
    int m = len [index];
    for (int j = 0; j < (m / 2); j++)
    {
      char tmp = words [index][j];
      words [index][j] = words [index][m - 1 - j];
      words [index][m - 1 - j] = tmp;
    }
  }

  void solve(bool emptyIsPal)
  {
    numPal [0] = 0;
    childStartIndex [0] = -1;
    currentIndexChild = 1;
    
    memset (numPal, 0, sizeof(int) * n * MAX_LEN * 26);
    memset (childStartIndex, -1, sizeof(int) * n * MAX_LEN * 26);

    for (int i = 0; i < n; i++)
    {
      _initPalSufix(i);
      addWordInTrie (i, words [i], emptyIsPal);
    }

    for (int i = 0; i < n; i++)
      visitWord (words [i], i);
  }

  int main()
  {
    input();
    sol = 0;
    solve(true);
    for (int i = 0; i < n; i++)
      r (i);
    solve(false);
    output();

    return 0;
  }