Use Manaker's algorithm

try kookko
ans: kook

String can have size 1000, max size is not 999.

Use hashs + bin find :)

 longest palindromic substring is "kazak" itself. What am i missing ?

Help me please!

#include <iostream>
#include <string>
#include<vector>
using namespace std;
string turn(string s)
{
    string news;
    for (int i = s.length() - 1; i >= 0; i--)
        news.push_back(s[i]);
    return news;
}
int main()
{
    string s; string news;
    getline(cin, s);
    vector <int> l;
    vector <string> counts;
    for (int i = 0; i < s.length(); i++)
    {
        int n = s.length();
        for (int j = 1; j <= s.length() - n + 1 && (s.length() - n + 1) <= (s.length() - i); j++)
        {
            news = s.substr(i, j);
            if (turn(news) == news && news.length() > 1)
            {
                l.push_back(news.length()); counts.push_back(news);
            }
            n--;
        }

    }
    int maxl = 0; string saves;
    for (int k = 0; k < l.size(); k++)
    {
        if (l[k] > maxl)
        {
            maxl = l[k]; saves = counts[k];
        }
    }
    cout << saves;
}

Try this simple test:
11123
Answer:
111

input : ABCDLKOIKJTFIDCBA

ouput is a single letter such as A K and I
NOT “ABCD” or what have you .

Hi! I'm just amazed about this algorithm! My previous O(N^3) implementation take 0.624 and 508 KB with my best efforts to reduce runtime. When I submitted the Manacher's one, the runtime dropped down to 0.015 and 2376 KB!! Just google it. It's a very easy and efficient O(N) algorithm. That's all you need to solve this problem. No more than 30 lines of code.

wa18 ...please

my cpp code is following:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int N = 5010, INF = 0x3f3f3f3f;

int c[N], sa[N], x[N], y[N];

void GetSA(int *r, int *sa, int n, int m)
{
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[i] = r[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) if (c[x[i]]) sa[c[x[i]]--] = i;
    for (int k = 1, p = 0; k <= n; k <<= 1, p = 0)
    {
        for (int i = n - k + 1; i <= n; i++) y[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y); x[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
        if (p == n) break; m = p;
    }
}

int hei[N], rnk[N];

void GetH(int *r, int *sa, int n)
{
    for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (int i = 1, k = 0, j; i <= n; hei[rnk[i++]] = k)
        for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++);
}

int n;

int s[N];
char str[N];

bool check(int a, int b, int len)
{
    return n - a + 2 == b + len;
}

int main()
{
    int mx = 0;
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    for (int i = 1; i <= len; i++) s[i] = str[i], mx = max(mx, s[i]);
    s[len + 1] = '$';
    for (int i = len; i >= 1; i--) s[len * 2 - i + 2] = str[i];
    n = (len << 1) + 1;
    GetSA(s, sa, n, 1000);
    GetH(s, sa, n);
    P ans = P(1, -1);
    for (int i = 3; i <= n; i++)
    {
        int a = max(sa[i - 1], sa[i]), b = min(sa[i - 1], sa[i]);
        if (!(a > len + 1 && b <= len)) continue;
        if (check(a, b, hei[i]) && P(hei[i], -b) > ans) ans = P(hei[i], -b);
    }
    int pos = -ans.se;
    for (int i = pos; i < pos + ans.fi; i++) printf("%c", str[i]); puts("");
    return 0;
}

I've tried to enlarge the alphabet size, but there's no effect.

I also test lots of random test cases, all of them are correct.

I hope someone could give me a hack data.

Edited by author 21.02.2019 15:57

Test: ABBCC
Answer: BB

'qwerSOMETEXTrewq' isn`t 19 test.

Hi, everyone!
I used Manacher's algorithm to solve this problem, but I got WA on #14 test. Can someone hint me, what could be the problem?

My code in python 3.6:

def is_palindrom(x):
    if x==x[::-1]:
        return True
    return False

s=input()
s=s[::-1]
n=len(s)
a=[]
for x in range(2,n+1):
    for i in range(0,n-x+1):
        if is_palindrom(s[i:i+x]):
            a.append(s[i:i+x])
if len(a)==0:
    b=s[-1]
else:
    b=a[-1]
print(b)

Memory is 70160 Kb, where so much it?
Please, help, I would be grateful!

I was so upset that I wa on #7 more than 10. I want to practice my suffix array,so I used it and used RMQ,But I wa on #7.
I very want to know what is #7.
Can the admin give the simple to me? thanks a lot
http://paste.ubuntu.com/23169621/
the suffix array algorithm is right cause I got AC ever using this Template~~

tried all mentioned test cases .all correct. still WA on #12.
using surfix array.any idea?

code here:

#include <cstdio>
#include <cstring>
int const N=220000;
int st[256], rank[2*N], rank1[2*N], count[N], tmp[N];
char a[N], b[N], s[N], max1;
int sa[N], height[N], si;
int main(){
    memset(st, 0, sizeof st);
    memset(rank, 0, sizeof rank);
    memset(rank1, 0, sizeof rank1);
    scanf("%s", b);
    int n1=strlen(b);
    for(int i=1; i<=n1; ++i)a[i]=b[i-1];
    for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i];
    a[0]=' ';
    a[n1+1]='#';
    int n=2*n1+1;
    a[n+1]='&';
    for(int i=1; i<=n; ++i)st[a[i]]=1;
    for(int i=1; i<=255; ++i)st[i]+=st[i-1];
    for(int i=1; i<=n; ++i)rank[i]=st[a[i]];

    int k=0;
    for(int p=1; k!=n; p+=p){
        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i+p]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;

        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];

        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for(int i=2; i<=n; ++i){
            if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k;
            rank[sa[i]]=k;
        }
    }
    k=0;
    for(int i=1; i<=n; ++i){
        if(rank[i]==1){
            k=0;
        }else{
            --k;
            if(k<0)k=0;
            while(a[i+k]==a[sa[rank[i]-1]+k])++k;
        }
        height[rank[i]]=k;
    }

    int max=-1;
    for(int i=2; i<=n; ++i){
        int p=sa[i];
        int q=sa[i-1];
        if((p-1)/n1 != (q-1)/n1){
            if(p+q+height[i]==n+2){
                if(height[i]>max){
                    max=height[i];
                    si=p;
                }
            }
        }
    }
    for(int i=si; i<si+max; ++i)printf("%c", a[i]);
    return 0;
}

THX :)

Try test abbc.
Good luck!

My Code perfect AC  with Visual Studio 2013, G++ 4.9, G++ 4.9 C++11.
But Clang 3.5 gives output limit exceeded, or access violation....
Submit codes
7217044
7217043