Ideone.com

fork download

copy

//karanaggarwal
#include<bits/stdc++.h>
using namespace std;
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define si(x) scanf("%d",&x)
#define F first
#define S second
#define PB push_back
#define MP make_pair
 
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
 
const int MAXN = 1000000;
 
void preProcess(string &s, string &ret) 
{
    int n = s.length();
    ret = "^";
    if (n == 0){ret+='$'; return;}
    for (int i = 0; i < n; i++)
    {
        ret += '#';
        ret += s[i];
    }
    ret += "#$";
}
 
void longestPalindrome(string &s, VI &P) 
{
    string T; 
    preProcess(s,T);
    int n = T.length();
    P.resize(n);
    int C = 0, R = 0;
    for (int i = 1; i < n-1; i++) {
        int i_mirror = 2*C-i; // equals to i' = C - (i-C)
 
        P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
        while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
            P[i]++;
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }
    for(int i =0; i < s.length(); i++)
        P[i] =   (P[2 + 2*i]+1)/2; 
    P.resize(s.length());
}
 
 
 
struct node
{
    int suff_link, len, next[26];
    int F[2];
};
int len;
node tree[MAXN+5];
int suff,num;
 
void init()
{
    suff = num = 2; 
    tree[1].len = -1; tree[1].suff_link = 1;
    tree[2].len = 0; tree[2].suff_link = 1;
}
void add_letter(int pos, string &s, int ty)
{
    int cur = suff;
    int curlen = 0; 
    while(1)
    {
        curlen = tree[cur].len;
        if(pos > curlen and s[pos - (1+curlen)]==s[pos]) break;
        cur = tree[cur].suff_link;
    }
    suff = tree[cur].next[s[pos]-'a'];
    if(suff)
    {
        if(tree[suff].F[ty]==0) tree[suff].F[ty] = pos;
        return;
    }
    suff = ++num;
    tree[suff].len = 2 + tree[cur].len;
    if(tree[suff].F[ty]==0) tree[suff].F[ty] = pos;
    tree[cur].next[s[pos]-'a'] = suff;
    if(tree[suff].len ==1)
    {
        tree[suff].suff_link = 2;
        return;
    }
    while(1)
    {
        cur = tree[cur].suff_link;
        curlen = tree[cur].len;
        if(pos > curlen and s[pos - (1+curlen)]==s[pos])
        {
            tree[suff].suff_link =  tree[cur].next[s[pos]-'a'];
            return;
        }
    }
}
 
 
int main()
{
    int t; si(t);
    while(t--)
    {
        VI A;
        string s; cin>>s; longestPalindrome(s,A);
        int n = s.length(); 
        vector<int> B(n+1,0);
        for(int i =0; i<=n+2; i++)
        {
            memset(tree[i].next, 0, sizeof(tree[i].next));
            tree[i].F[0] = tree[i].F[1] = 0; 
        }
        init();
        for(int i =0; i<n; i++)
            add_letter(i,s,0);
        reverse(s.begin(),s.end());
        suff = 2;
        for(int i =0; i<n; i++)
            add_letter(i,s,1);
        for(int i =3; i<=num; i++)
        {
            tree[i].F[1] = n - 1 - tree[i].F[1];
            if(tree[i].F[0]>=tree[i].F[1])
            {
                B[tree[i].F[1]]++;
                B[tree[i].F[0] + 1]--;
            }
        }
        int total = num - 2; 
        int mx = 0; 
        for(int i =0; i<n; i++)
        {
            if(i) B[i] += B[i-1];
            mx = max(mx, total - B[i] + A[i]);
        }
        int cnt =0; 
        for(int i =0; i<n;i++) if(mx==total-B[i] + A[i]) cnt++;
        printf("%d %d\n",mx,cnt);
    }
    return 0;	
}

Ly9rYXJhbmFnZ2Fyd2FsCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIFRSQUNFCiNpZmRlZiBUUkFDRQojZGVmaW5lIHRyYWNlKC4uLikgX19mKCNfX1ZBX0FSR1NfXywgX19WQV9BUkdTX18pCnRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxPgp2b2lkIF9fZihjb25zdCBjaGFyKiBuYW1lLCBBcmcxJiYgYXJnMSl7CiAgICBjZXJyIDw8IG5hbWUgPDwgIiA6ICIgPDwgYXJnMSA8PCBzdGQ6OmVuZGw7Cn0KdGVtcGxhdGUgPHR5cGVuYW1lIEFyZzEsIHR5cGVuYW1lLi4uIEFyZ3M+CnZvaWQgX19mKGNvbnN0IGNoYXIqIG5hbWVzLCBBcmcxJiYgYXJnMSwgQXJncyYmLi4uIGFyZ3MpewogICAgY29uc3QgY2hhciogY29tbWEgPSBzdHJjaHIobmFtZXMgKyAxLCAnLCcpO2NlcnIud3JpdGUobmFtZXMsIGNvbW1hIC0gbmFtZXMpIDw8ICIgOiAiIDw8IGFyZzE8PCIgfCAiO19fZihjb21tYSsxLCBhcmdzLi4uKTsKfQojZWxzZQojZGVmaW5lIHRyYWNlKC4uLikKI2VuZGlmCgojZGVmaW5lIHNpKHgpIHNjYW5mKCIlZCIsJngpCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTVAgbWFrZV9wYWlyCgp0eXBlZGVmIGxvbmcgbG9uZyBMTDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IFBJSTsKdHlwZWRlZiB2ZWN0b3I8aW50PiBWSTsKdHlwZWRlZiB2ZWN0b3I8UElJPiBWUElJOwoKY29uc3QgaW50IE1BWE4gPSAxMDAwMDAwOwoKdm9pZCBwcmVQcm9jZXNzKHN0cmluZyAmcywgc3RyaW5nICZyZXQpIAp7CiAgICBpbnQgbiA9IHMubGVuZ3RoKCk7CiAgICByZXQgPSAiXiI7CiAgICBpZiAobiA9PSAwKXtyZXQrPSckJzsgcmV0dXJuO30KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIHJldCArPSAnIyc7CiAgICAgICAgcmV0ICs9IHNbaV07CiAgICB9CiAgICByZXQgKz0gIiMkIjsKfQoKdm9pZCBsb25nZXN0UGFsaW5kcm9tZShzdHJpbmcgJnMsIFZJICZQKSAKewogICAgc3RyaW5nIFQ7IAogICAgcHJlUHJvY2VzcyhzLFQpOwogICAgaW50IG4gPSBULmxlbmd0aCgpOwogICAgUC5yZXNpemUobik7CiAgICBpbnQgQyA9IDAsIFIgPSAwOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuLTE7IGkrKykgewogICAgICAgIGludCBpX21pcnJvciA9IDIqQy1pOyAvLyBlcXVhbHMgdG8gaScgPSBDIC0gKGktQykKCiAgICAgICAgUFtpXSA9IChSID4gaSkgPyBtaW4oUi1pLCBQW2lfbWlycm9yXSkgOiAwOwogICAgICAgIHdoaWxlIChUW2kgKyAxICsgUFtpXV0gPT0gVFtpIC0gMSAtIFBbaV1dKQogICAgICAgICAgICBQW2ldKys7CiAgICAgICAgaWYgKGkgKyBQW2ldID4gUikgewogICAgICAgICAgICBDID0gaTsKICAgICAgICAgICAgUiA9IGkgKyBQW2ldOwogICAgICAgIH0KICAgIH0KICAgIGZvcihpbnQgaSA9MDsgaSA8IHMubGVuZ3RoKCk7IGkrKykKICAgICAgICBQW2ldID0gICAoUFsyICsgMippXSsxKS8yOyAKICAgIFAucmVzaXplKHMubGVuZ3RoKCkpOwp9CgoKCnN0cnVjdCBub2RlCnsKICAgIGludCBzdWZmX2xpbmssIGxlbiwgbmV4dFsyNl07CiAgICBpbnQgRlsyXTsKfTsKaW50IGxlbjsKbm9kZSB0cmVlW01BWE4rNV07CmludCBzdWZmLG51bTsKCnZvaWQgaW5pdCgpCnsKICAgIHN1ZmYgPSBudW0gPSAyOyAKICAgIHRyZWVbMV0ubGVuID0gLTE7IHRyZWVbMV0uc3VmZl9saW5rID0gMTsKICAgIHRyZWVbMl0ubGVuID0gMDsgdHJlZVsyXS5zdWZmX2xpbmsgPSAxOwp9CnZvaWQgYWRkX2xldHRlcihpbnQgcG9zLCBzdHJpbmcgJnMsIGludCB0eSkKewogICAgaW50IGN1ciA9IHN1ZmY7CiAgICBpbnQgY3VybGVuID0gMDsgCiAgICB3aGlsZSgxKQogICAgewogICAgICAgIGN1cmxlbiA9IHRyZWVbY3VyXS5sZW47CiAgICAgICAgaWYocG9zID4gY3VybGVuIGFuZCBzW3BvcyAtICgxK2N1cmxlbildPT1zW3Bvc10pIGJyZWFrOwogICAgICAgIGN1ciA9IHRyZWVbY3VyXS5zdWZmX2xpbms7CiAgICB9CiAgICBzdWZmID0gdHJlZVtjdXJdLm5leHRbc1twb3NdLSdhJ107CiAgICBpZihzdWZmKQogICAgewogICAgICAgIGlmKHRyZWVbc3VmZl0uRlt0eV09PTApIHRyZWVbc3VmZl0uRlt0eV0gPSBwb3M7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgc3VmZiA9ICsrbnVtOwogICAgdHJlZVtzdWZmXS5sZW4gPSAyICsgdHJlZVtjdXJdLmxlbjsKICAgIGlmKHRyZWVbc3VmZl0uRlt0eV09PTApIHRyZWVbc3VmZl0uRlt0eV0gPSBwb3M7CiAgICB0cmVlW2N1cl0ubmV4dFtzW3Bvc10tJ2EnXSA9IHN1ZmY7CiAgICBpZih0cmVlW3N1ZmZdLmxlbiA9PTEpCiAgICB7CiAgICAgICAgdHJlZVtzdWZmXS5zdWZmX2xpbmsgPSAyOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIHdoaWxlKDEpCiAgICB7CiAgICAgICAgY3VyID0gdHJlZVtjdXJdLnN1ZmZfbGluazsKICAgICAgICBjdXJsZW4gPSB0cmVlW2N1cl0ubGVuOwogICAgICAgIGlmKHBvcyA+IGN1cmxlbiBhbmQgc1twb3MgLSAoMStjdXJsZW4pXT09c1twb3NdKQogICAgICAgIHsKICAgICAgICAgICAgdHJlZVtzdWZmXS5zdWZmX2xpbmsgPSAgdHJlZVtjdXJdLm5leHRbc1twb3NdLSdhJ107CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICB9Cn0KCgppbnQgbWFpbigpCnsKICAgIGludCB0OyBzaSh0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBWSSBBOwogICAgICAgIHN0cmluZyBzOyBjaW4+PnM7IGxvbmdlc3RQYWxpbmRyb21lKHMsQSk7CiAgICAgICAgaW50IG4gPSBzLmxlbmd0aCgpOyAKICAgICAgICB2ZWN0b3I8aW50PiBCKG4rMSwwKTsKICAgICAgICBmb3IoaW50IGkgPTA7IGk8PW4rMjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgbWVtc2V0KHRyZWVbaV0ubmV4dCwgMCwgc2l6ZW9mKHRyZWVbaV0ubmV4dCkpOwogICAgICAgICAgICB0cmVlW2ldLkZbMF0gPSB0cmVlW2ldLkZbMV0gPSAwOyAKICAgICAgICB9CiAgICAgICAgaW5pdCgpOwogICAgICAgIGZvcihpbnQgaSA9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIGFkZF9sZXR0ZXIoaSxzLDApOwogICAgICAgIHJldmVyc2Uocy5iZWdpbigpLHMuZW5kKCkpOwogICAgICAgIHN1ZmYgPSAyOwogICAgICAgIGZvcihpbnQgaSA9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIGFkZF9sZXR0ZXIoaSxzLDEpOwogICAgICAgIGZvcihpbnQgaSA9MzsgaTw9bnVtOyBpKyspCiAgICAgICAgewogICAgICAgICAgICB0cmVlW2ldLkZbMV0gPSBuIC0gMSAtIHRyZWVbaV0uRlsxXTsKICAgICAgICAgICAgaWYodHJlZVtpXS5GWzBdPj10cmVlW2ldLkZbMV0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIEJbdHJlZVtpXS5GWzFdXSsrOwogICAgICAgICAgICAgICAgQlt0cmVlW2ldLkZbMF0gKyAxXS0tOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGludCB0b3RhbCA9IG51bSAtIDI7IAogICAgICAgIGludCBteCA9IDA7IAogICAgICAgIGZvcihpbnQgaSA9MDsgaTxuOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpZihpKSBCW2ldICs9IEJbaS0xXTsKICAgICAgICAgICAgbXggPSBtYXgobXgsIHRvdGFsIC0gQltpXSArIEFbaV0pOwogICAgICAgIH0KICAgICAgICBpbnQgY250ID0wOyAKICAgICAgICBmb3IoaW50IGkgPTA7IGk8bjtpKyspIGlmKG14PT10b3RhbC1CW2ldICsgQVtpXSkgY250Kys7CiAgICAgICAgcHJpbnRmKCIlZCAlZFxuIixteCxjbnQpOwogICAgfQogICAgcmV0dXJuIDA7CQp9

Runtime error #stdin #stdout 0.01s 120640KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/bxH8O0

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language