BISHI92 【模板】前缀函数（kmp）

思路求解代码publicstaticvoidmain(String[]args)throwsIOException{// 创建缓冲读取器用于从标准输入读取数据BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));// 创建打印输出器用于向标准输出打印数据PrintWriteroutnewPrintWriter(newOutputStreamWriter(System.out));// 读取测试用例的数量TintTInteger.parseInt(br.readLine().trim());// 处理每个测试用例while(T--0){// 读取一行输入并分割成字符串数组String[]sbr.readLine().trim().split(\\s);// 获取字符串的长度nintnInteger.parseInt(s[0]);// 计算前缀函数数组int[]picomputePre(s[1],n);// 输出前缀函数数组元素间用空格分隔for(inti0;in;i){out.print(pi[i](in-1?: ));}// 换行out.println();}// 刷新输出缓冲区确保所有输出都被写出out.flush();// 关闭输出流out.close();// 关闭输入流br.close();}/** * 计算字符串的前缀函数Prefix Function * 前缀函数pi[i]表示字符串s[0..i]的最长相等前后缀的长度不包括s[0..i]本身 * * param s 输入的字符串 * param n 字符串的长度 * return 返回前缀函数数组pi其中pi[i]表示s[0..i]的最长相等前后缀长度 */privatestaticint[]computePre(Strings,intn){int[]pinewint[n];// 初始化前缀函数数组长度为n// 从第二个字符开始遍历字符串for(inti1;in;i){intjpi[i-1];// 初始化j为前一个字符的前缀函数值// 当j大于0且当前字符不匹配时通过前缀函数回退while(j0s.charAt(i)!s.charAt(j)){jpi[j-1];// 回退到前一个可能匹配的位置}// 如果当前字符匹配则增加匹配长度if(s.charAt(i)s.charAt(j)){j;}// 将当前字符的前缀函数值存入数组pi[i]j;}returnpi;// 返回计算得到的前缀函数数组}