[bzoj4236]JOIOJI

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。

最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。

JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。

现在JOIOJI桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。

n<=2*10^5

 

就是个哈希qaq

假设三种字母的数量分别是a,b,c

那么数量相同的字串，a-b b-c c-a肯定都相同，拿出来哈希一下就好了。

#include<iostream>

#include<cstdio>

#include<map>

#define MN 200000

#define magic 73

#define magic2 233333333

#define ll long long

using namespace std;

int X;char ch;

inline int read()

{

    X =  , ch = getchar();

    while(ch < '' || ch > '') ch = getchar();

    while(ch >= '' && ch <= ''){X = X *  + ch - '';ch = getchar();}

    return X;

}

int a,b,c,n,ans=;

char st[MN+];

map<ll,int> mp;

void ins(int num)

{

    ll hash=(1LL*(b-a+magic)*magic+(b-c+magic))*magic2+c-a;

    int t=mp[hash];

    if(t) ans=max(ans,num-t+);

    else mp[hash]=num+;

}

int main()

{

    n=read();scanf("%s",st+);ins();

    for(int i=;i<=n;i++)

    {

        st[i]=='J'?a++:(st[i]=='O'?b++:c++);

        ins(i);

    }

    printf("%d\n",ans);

    return ;

}