题解 | #白兔的字符串#

Java版看这里

已知目标串为str，需要再strs里面遍历寻找每一个母串所含有的子串的循环同构的串，那针对已知的子串，可以预处理得到所有目标子串，我们再将所有目标串放入Set中，方便后续判断。

具体做法为： 如果有一个串为：abcd 那么其循环同构的串即为 abcd + abc = abcdabc 中的所有长度为原串长度的子串

abcd abc | a bcda bc | ab cdab c |abc dabc

后续的子串个数比较即为基础的字符串hash

附上AC代码：

import java.io.*;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static BufferedReader re = new BufferedReader(new InputStreamReader(System.in));// 快速输入
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));// 快速输出

    public static final int N = 131;
    public static long[] p = new long[1000001];

    public static void main(String[] args) throws IOException {
        init();
        String str = sc.next();
        int n = str.length();
      	// 更新str并计算所有目标子串，将其放入Set中
        str += str.substring(0, str.length() - 1);

        long[] tn = new long[str.length()];
        tn[0] = str.charAt(0);
        for (int i = 1; i < str.length(); i++) {
            tn[i] = tn[i - 1] * N + str.charAt(i);
        }

        Set<Long> ts = new HashSet<>();
        for (int i = 0; i <= str.length() - n; i++) {
            long tmp=get(tn, i, i + n - 1);
            ts.add(tmp);
        }

      	// 遍历所有母串
        int t = sc.nextInt();
        while (t-- > 0) {
            str = sc.next();
			
          	// 计算当前母串的hash数组（计算方法和之前的str一样）
            tn = new long[str.length()];
            tn[0] = str.charAt(0);
            for (int i = 1; i < str.length(); i++) {
                tn[i] = tn[i - 1] * N + str.charAt(i);
            }
            
            // 寻找目标串
            int cnt = 0;
            for (int i = 0; i <= str.length() - n; i++) {
                // 判断每一个长度为n的子串
                long tmp=get(tn, i, i + n - 1);
                if (ts.contains(tmp)) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }

    public static void init() {
      	// 初始化N的幂数组
        p[0] = 1;
        for (int i = 1; i < 1000001; i++) {
            p[i] = p[i-1] * N;
        }
    }

    public static long get(long[] nums, int l, int r) {
      	//通过传入的hash数组和截取范围返回对应的hash值（包头包尾）
        return l == 0 ? nums[r] : (nums[r] - p[r - l + 1] * nums[l - 1]);
    }
}