题目：字符串匹配

思路：

1. 字符串是否一样可以使用hash进行辅助计算，计算每一个字符串的哈希值，通过比较哈希值是否一样判断两个字符串是否一样。
2. ASCII的最大值是127，因此p可以选择131或者更大的质数。

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	static int mod=1_000_000_007;
	public static void main(String[] args) throws IOException {
		String s=br.readLine();
		String t=br.readLine();
		int p=131;
		//记录字符串t的哈希值
		int tgh=0;
		//记录2^n的值
		int h=1;
		char[] ct=t.toCharArray();
		int n=ct.length;
		for(int i=0;i<n;i++) {
			tgh=tgh*p+ct[i]+1;
			h=h*p;
		}
		char[] cs=s.toCharArray();
		int m=cs.length;
		int[] pre=new int[m];
		for(int i=0;i<n;i++) {
			if(i==0) {
				pre[i]=cs[i]+1;
				continue;
			}
			pre[i]=pre[i-1]*p+cs[i]+1;
		}
		int cnt=0;
		if(pre[n-1]==tgh) {
			pw.print(1+" ");
			cnt++;
		}
		for(int i=n,j=0;i<m;i++,j++) {
			pre[i]=pre[i-1]*p+cs[i]+1;
			if(pre[i]-pre[j]*h==tgh) {
				pw.print((j+2)+" ");
				cnt++;
			}
		}
        if(cnt==0) {
        	pw.print(-1);
        }
		pw.flush();
	}
}