bzoj4236 JOIOJI hash 模拟

时间:2023-12-25 20:31:01
JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。
最近,JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成,并且想让“J、O、I”三个字母的出现次数恰好相同。
JOIOJI桑家有一份祖传的卷轴,上面写着一首长诗,长度为N,由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。
现在JOIOJI桑将这首长诗交给了你,请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。

Input

第一行一个正整数N,代表这首长诗的长度
接下来一行一个长度为N的字符串S,表示这首长诗,保证每个字符都是“J、O、I”三个字母中的一个

Output

输出一行一个正整数,代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串,输出0

Sample Input

10
JOIIJOJOOI

Sample Output

6

Hint

选择“IIJOJO”这个子串,长度为6,包含“J、O、I”三个字母各2个,这是最长的满足要求的子串。

1<=N<=2*10^5

题解

 这道题目是有些巧妙的,一段连续的区间j,o,i三个字母出现次数相等。

 比如i行和j行之间是的,那么满足,J[j]-J[i]=O[j]-O[i]=I[j]-I[i]=x,

 那么可以得到,J[i]-O[i]=J[j]-O[j],另外一组也是一样的,然后就是双HASH判断了。

 #include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 200200
using namespace std;
int n,ans;
char s[M];
map<pair<int,int>,int> m;
int sum[][M];
int main()
{
int i;
cin>>n;
scanf("%s",s+);
m[make_pair(,)]=;
for(i=;i<=n;i++)
{
sum[][i]=sum[][i-]+(s[i]=='J');
sum[][i]=sum[][i-]+(s[i]=='O');
sum[][i]=sum[][i-]+(s[i]=='I');
if( m.find( make_pair(sum[][i]-sum[][i],sum[][i]-sum[][i]) )==m.end() )
m[make_pair(sum[][i]-sum[][i],sum[][i]-sum[][i])]=i;
else ans=max(ans,i-m[make_pair(sum[][i]-sum[][i],sum[][i]-sum[][i])]);
}
cout<<ans<<endl;
}