# NOIP2020正式赛 字符串匹配 （string）题解

2020-12-17 14:10:01

84pts的想法比较显然（虽说我这个菜逼想了近1h）

5亿左右的复杂度不能过，我们可以将 l o g n log n logn l o g 26 log 26 log26分开

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N (1<<20)+5
#define mo1 1000000007
#define mo2 19260817
#define ll long long
#define lowbit(x) x&(-x)
#define R register
#define I inline
#define ull unsigned long long
using namespace std;
ll tree[27];
short sum[N],js[27],qz;
ull hx1[N],hx2[N];
ull mi1,mi2,g1;
char c[N];
int main()
{

freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
R int cs;
scanf("%d\n",&cs);
while (cs--)
{

scanf("%s\n",c+1);
R int n=strlen(c+1);memset(tree,0,sizeof(tree));memset(js,0,sizeof(js));
R ll ans=0;
sum[n+1]=0;
for (R int i=1;i<=n;i++) hx1[i]=hx1[i-1]*27+(c[i]-'a');
for (R int i=n;i>=1;i--)
{

js[c[i]-'a']^=1;
sum[i]=sum[i+1]+(js[c[i]-'a']%2?1:-1);
} memset(js,0,sizeof(js));
js[0]=0,js[c[1]-'a']=1;
for (R int i=1;i<=26;i++) tree[i]++;
qz=1;mi1=mi2=27;
for (R int i=2;i<=n-1;i++)
{

g1=0;
mi1=mi1*27;
for (R int j=1;j<=n/i;j++)
{

g1=g1*mi1+hx1[i];
if (j*i>=n) break;
if (g1==hx1[j*i])
{

ans+=tree[sum[j*i+1]];
} else break;
}
js[c[i]-'a']^=1;
qz+=(!(js[c[i]-'a']&1))?-1:1;
for (R int j=qz;j<=26;j++) tree[j]++;
}
printf("%lld\n",ans);
}
return 0;
}

https://my.oschina.net/u/4321646/blog/4812784