思想
基于字符串哈希的字符串循环移位,将1~i移动到字符串最后面:(h[n]-h[i]p[n-i])p[i]+h[i]。
代码
import java.io.*;
import java.util.HashSet;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static HashSet<Long> set = new HashSet<>();
static int N = 1000010, n; //为了保证字符串哈希的有效性,这里用了两个质数来计算字符串哈希
static long P=131, Q = Long.MAX_VALUE;
static long[] h = new long[N];
static long[] p = new long[N];
public static void main(String[] args)throws IOException{
int n = Integer.parseInt(in.readLine());
String s = " "+in.readLine();
char[] c = s.toCharArray();
//计算字符串哈希
p[0] = 1;
for(int i=1; i<=n; i++){
p[i] = (p[i-1]*P)%Q;
h[i] = ((h[i-1]*P)%Q+c[i])%Q;
}
//将1~i的前缀放到字符串后面
for(int i=1; i<=n; i++){
set.add((h[n]-h[i]*p[n-i])*p[i]+h[i]);
}
out.println(set.size());
out.flush();
out.close();
}
}