secvpal

Pentru un şir de caractere $S$, vom nota cu $lmax[S]$ lungimea maximă a unei secvenţe palindromice conţinută în şirul $S$. Astfel, pentru şirul S = abAabaabC, $lmax[S]=4$, iar pentru şirul S = a, $lmax[S]=1$. Prin secvenţa palindromică a unui şir $S$ înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.

Cerinţă

Date fiind $N$ şiruri de caractere $S_{1}, S_{2},…, S_{n}$ şi o valoare naturală $L$, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: $S_{i}, S_{i+1}, … , S_{j}$, cu $i \leq j$, pentru care $lmax[S_{i}]+lmax[S_{i+1}]+ ... +lmax[S_{j}]=L$.

Date de intrare

Fişierul de intrare secvpal.in conţine pe prima linie două numere naturale $N$, $L$ cu semnificaţia din enunţ, iar pe fiecare dintre următoarele $N$ linii, câte un şir de caractere.

Date de ieșire

Fişierul de ieşire secvpal.out va conţine pe o singură linie un număr natural nr ce reprezintă numărul de secvenţe de şiruri de caractere ce îndeplinesc condiţia cerută.

Restricții și precizări

• $2 \leq N \leq 50 \ 000$;
• $0 \leq nr \leq 10 \ 000$;
• $1 \leq$ lungimea maximă a oricărui şir $S_{i} \leq 10 \ 000$, $1 \leq i \leq N$;
• $1 \leq$ lungimea maximă a unei secvenţe palindromice lmax($S_{i}$) $\leq 1 \ 000$;
• $1 \leq (\text{lungimea maximă şir }S_{i}) \times N \leq 1 \ 000 \ 000$;
• Cele $N$ şiruri de caractere conţin doar caracterele A..Z,a..z;
• Un palindrom este un şir de caractere care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi.

Exemplul 1

secvpal.in

5 11
aCCACCACaBa
AAPAPAACCAA
acaacc
capac
CACAACAACACCAACP

secvpal.out

2

Explicație

1. $lmax(”aCCACCACaBa”)=6$
2. $lmax(”AAPAPAACCAA”)=7$
3. $lmax(”acaacc”)=4$
4. $lmax(”capac”)=5$
5. $lmax(”CACAACAACACCAACP”)=11$

Cele două secvenţe de lungime $11$ sunt: $2,3$ şi $5$