TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

palap.cpp    3,297 b      izvorni kod rešenja
palap.tests.7z    663,393 b      test primeri

zadatak: PalaP

Dat je niz reči (wi) dužine n. Uz pomoć ovih reči moguće je kreirati n2 parova (wi, wj) reči, čijom konkatenacijom dobijamo reč wij. 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.

palap.in      palap.out
3
a
aa
ab
        
5

Objašnjenje.

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

fajl: palap.cpp
#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;
  }