河南萌新联赛2024第（二）场：南阳理工学院 E - “好”字符

河南萌新联赛2024第（二）场：南阳理工学院 E - “好”字符

题目描述

字符串的循环同构：表示把字符串的左边第一位移到最后一位，新串再进行这样的操作，得到的一些字符串都是原串的循环同构，例如"bcda"、“cdab”、"dabc"都是"abcd"的循环同构。

给你两个长度相等的字符串 a 和 b ，字符串 a 和 b 均由小写字母组成。当某个字符 x 在字符串 a 与字符串 b 或 b 的循环同构中出现的所有位置依次对应时（对于字符串的每一位，要么 a 和 b 的这一位都是该字符，要么都不为该字符）,称该字符为“好”字符。例如：当 a = “acba”，b = "bdaa"时，字符’a’与字符’b’为“好”字符
现在，我们想请你判断字符串 a 与字符串 b 中“好”字符的数量

输入描述

第一行给你一个 $n（1<n<10^6）$，$n$ 为字符串 $a$ 与 $b$ 的长度。
第二行与第三行为字符串 $a$ 和 $b$ ， $a$ 和 $b$ 均由小写字母组成。

输出描述:

单行输出一个数字，表示“好”字符的个数。

输入

6
acabxb
eababf
1
2
3

输出

2
1

说明 当b的循环同构体为"ababfe"时，字符’a’为“好”字符，当b的循环同构体为"feabab"时，字符’b’为“好”字符。

输入

3
abc
cde
1
2
3

输出

1
1

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;

const int N=1000010,P=13331;

ULL p[N*2],h1[N*2],h2[N];

void geth(string &s,char c,ULL h[])
{
	for(int i=1; i<=s.size(); i++)
		h[i]=h[i-1]*P+(s[i]==c);
}

ULL get(ULL h[],int l, int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
	int n;cin>>n;
	string a,b;cin>>a>>b;
	
	unordered_set<char> st(a.begin(),a.end());
	a=' '+a+a;
	b=' '+b;
	
    p[0]=1;
	for(int i=1; i<=2000000; i++) p[i]=p[i-1]*P;
	
	int res=0;
	for(auto c:st)
	{
		geth(a,c,h1);
		geth(b,c,h2);
		
		for(int i=1; i<=n; i++)
			if(get(h1,i,i+n-1)==get(h2,1,n))
			{
				res++;
				break;
			}
	}
	cout<<res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47