HDU 5677 ztr loves substring

Problem Description

ztr love reserach substring.Today ,he has n string.Now ztr want to konw,can he take out exactly k palindrome from all substring of these n string,and thrn sum of length of these k substring is L.

for example string "yjqqaq"

this string contains plalindromes:"y","j","q","a","q","qq","qaq".

so we can choose "qq" and "qaq".

Input

T(T<=10) indicating the number of test cases.

For each test case:

First line contains these positive integer 

N(1<=N<=100),K(1<=K<=100),L(L<=100).

The next N line,each line contains a string only contains lowercase.Guarantee even length of string won't more than L.

Output

For each test,Output a line.If can output "True",else output "False".

Sample Input

3

2 3 7

yjqqaq

claris

2 2 7

popoqqq

fwwf

1 3 3

aaa

Sample Output

False

True

True

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
const int maxn = 1e2 + 10;
int T, n, w, m, c[maxn], f[maxn][maxn];
char s[maxn];

struct PalindromicTree
{
  const static int maxn = 1e5 + 10;
  const static int size = 26;
  int next[maxn][size], last, sz, tot;
  int fail[maxn], len[maxn], cnt[maxn];
  char s[maxn];
  int Node(int length)
  {
    memset(next[sz], 0, sizeof(next[sz]));
    len[sz] = length; cnt[sz] = 0; return sz++;
  }
  void clear()
  {
    sz = last = fail[2] = fail[1] = 1;
    Node(-1); Node(tot = 0);
  }
  void reset()
  {
    last = 1; tot = 0;
  }
  int getfail(int x)
  {
    while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
    return x;
  }
  void add(char pos)
  {
    int x = (s[++tot] = pos) - 'a', y = getfail(last);
    if (!(last = next[y][x]))
    {
      last = next[y][x] = Node(len[y] + 2);
      fail[last] = len[last] == 1 ? 2 : next[getfail(fail[y])][x];
    }
    ++cnt[last];
  }
  void work()
  {
    memset(f, 0, sizeof(f));
    memset(c, 0, sizeof(c));
    for (int i = sz - 1; i > 2; i--)
    {
      cnt[fail[i]] += cnt[i];
      c[len[i]] += cnt[i];
    }
    f[0][0] = 1;
    for (int i = 1; i <= 100; i++)
    {
      for (int j = 1; c[i] > 0; j <<= 1)
      {
        int a = i*(j <= c[i] ? j : c[i]), b = j <= c[i] ? j : c[i];
        c[i] -= j;
        for (int k = w; k >= b; k--)
        {
          for (int kk = m; kk >= a; kk--)
          {
            f[k][kk] = f[k][kk] || f[k - b][kk - a];
          }
        }
      }
    }
    printf("%s\n", f[w][m] ? "True" : "False");
  }
}solve;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d%d", &n, &w, &m);
    solve.clear();
    while (n--)
    {
      scanf("%s", s);   solve.reset();
      for (int i = 0; s[i]; i++) solve.add(s[i]);
    }
    solve.work();
  }
  return 0;
}