E. Ann and Half-Palindrome
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/557/problem/E
Description
On the last theoretical class the teacher introduced the notion of a half-palindrome.
String t is a half-palindrome, if for all the odd positions i () the following condition is held: ti = t|t| - i + 1, where |t| is the length of string t if positions are indexed from 1. For example, strings "abaa", "a", "bb", "abbbaa" are half-palindromes and strings "ab", "bba" and "aaabaa" are not.
Ann knows that on the exam she will get string s, consisting only of letters a and b, and number k. To get an excellent mark she has to find the k-th in the lexicographical order string among all substrings of s that are half-palyndromes. Note that each substring in this order is considered as many times as many times it occurs in s.
The teachers guarantees that the given number k doesn't exceed the number of substrings of the given string that are half-palindromes.
Can you cope with this problem?
Input
The first line of the input contains string s (1 ≤ |s| ≤ 5000), consisting only of characters 'a' and 'b', where |s| is the length of string s.
The second line contains a positive integer k — the lexicographical number of the requested string among all the half-palindrome substrings of the given string s. The strings are numbered starting from one.
It is guaranteed that number k doesn't exceed the number of substrings of the given string that are half-palindromes.
Output
Print a substring of the given string that is the k-th in the lexicographical order of all substrings of the given string that are half-palindromes.
Sample Input
abbabaab
7
Sample Output
abaa
HINT
题意
定义了半回文串，即奇数位置上的数是回文的
给你个字符串，在他的子串中，让你找到第k大的半回文子串
题解：
先暴力出回文串的子串
然后强行插入字典树，再强行dfs一下
超级大暴力就好了
代码来源于http://codeforces.com/contest/557/submission/11866823
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 5005
#define mod 10007
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** struct trie
{
int cnt,ch[];
};
int ok[maxn][maxn];
trie T[maxn*(maxn+)/];
trie null;
char res[maxn];
string s;
int k,ts,m=-,root,n;
int newnode()
{
T[++ts]=null;
return ts;
}
void add(int i)
{
int cur=root;
for(int j=i;j<n;j++)
{
if(T[cur].ch[s[j]-'a']==-)
T[cur].ch[s[j]-'a']=newnode();
cur=T[cur].ch[s[j]-'a'];
if(ok[i][j])
T[cur].cnt++;
}
}
void dfs(int cur)
{
k-=T[cur].cnt;
if (k<=) {
printf("%s",res);
exit();
}
if (T[cur].ch[]!=-) {
res[++m]='a';
dfs(T[cur].ch[]);
res[m]=;m--;
}
if (T[cur].ch[]!=-) {
res[++m]='b';
dfs(T[cur].ch[]);
res[m]=;m--;
}
}
int main()
{
cin>>s>>k;
n=s.size();
null.cnt=,null.ch[]=null.ch[]=-;
root=newnode();
for(int len=;len<=n;len++)
{
for(int i=;i<=n-len;i++)
{
int j=i+len-;
if(j-i<=)
ok[i][j]=(s[i]==s[j]);
else
ok[i][j]=(s[i]==s[j])&&ok[i+][j-];
}
}
for(int i=;i<n;i++)
add(i);
dfs(root);
}