|
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.
|
logo by Igor Antolović
|
|
|
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;
}
|
|
|