[文章目录]
Description
JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。
最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。
JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。
现在JOIOJI桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。
想到可以O（n）弄出一个'i' 'j' 'o'的前缀数，然后只要两个前缀数的差相同就说明这两个位置之间的字符串符合要求。搞一个map出来，二元组映射坐标。STL-map练手
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>//makepair用的
using namespace std;
int len,ans;
char st[210000];
int num[300],sumj,sumo,sumi;
map<pair<int ,int> ,int > v;
int main()
{
scanf("%d",&len);
scanf("%s",st+1);
int i,j;
if(len<=1000)
{
for(i=1;i<=len;i++)
{
num['J']=num['O']=num['I']=0;
for(j=i;j<=len;j++)
{
num[st[j]]++;
if((j-i+1)%3==0&&num['J']==num['O']&&num['J']==num['I'])
ans=max(ans,j-i+1);
}
}
printf("%d",ans);
}
else
{
for(int i=1;i<=len;i++)
{
if(st[i]=='J') sumj++;
if(st[i]=='O') sumo++;
if(st[i]=='I') sumi++;
if(v.find(make_pair(sumi-sumo,sumo-sumj))==v.end())
v[make_pair(sumi-sumo,sumo-sumj)]=i;
else ans=max(ans,i-v[make_pair(sumi-sumo,sumo-sumj)]);
}
printf("%d",ans);
}
return 0;
}