E. Ann and Half-Palindrome

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/557/problem/E

Description

Tomorrow Ann takes the hardest exam of programming where she should get an excellent mark.

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

Sample Output

abaa

HINT

题意

定义了半回文串，即奇数位置上的数是回文的

给你个字符串，在他的子串中，让你找到第k大的半回文子串

题解：

先暴力出回文串的子串

然后强行插入字典树，再强行dfs一下

超级大暴力就好了

代码来源于http://codeforces.com/contest/557/submission/11866823

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   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-9const int inf=0x3f3f3f3f;const ll infll = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************struct trie{ int cnt,ch[2];};int ok[maxn][maxn];trie T[maxn*(maxn+1)/2];trie null;char res[maxn];string s;int k,ts,m=-1,root,n;int newnode(){ T[++ts]=null; return ts;}void add(int i){ int cur=root; for(int j=i;j
                   
                    >s>>k; n=s.size(); null.cnt=0,null.ch[0]=null.ch[1]=-1; root=newnode(); for(int len=1;len<=n;len++) { for(int i=0;i<=n-len;i++) { int j=i+len-1; if(j-i<=3) ok[i][j]=(s[i]==s[j]); else ok[i][j]=(s[i]==s[j])&&ok[i+2][j-2]; } } for(int i=0;i

转载于:https://www.cnblogs.com/qscqesze/p/4612230.html

你可能感兴趣的文章