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

思路

求解代码

publicstaticvoidmain(String[]args)throwsIOException{// 创建缓冲读取器，用于从标准输入读取数据BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));// 创建打印输出器，用于向标准输出打印数据PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取测试用例的数量TintT=Integer.parseInt(br.readLine().trim());// 处理每个测试用例while(T-->0){// 读取一行输入并分割成字符串数组String[]s=br.readLine().trim().split("\\s+");// 获取字符串的长度nintn=Integer.parseInt(s[0]);// 计算前缀函数数组int[]pi=computePre(s[1],n);// 输出前缀函数数组，元素间用空格分隔for(inti=0;i<n;i++){out.print(pi[i]+(i==n-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[]pi=newint[n];// 初始化前缀函数数组，长度为n// 从第二个字符开始遍历字符串for(inti=1;i<n;i++){intj=pi[i-1];// 初始化j为前一个字符的前缀函数值// 当j大于0且当前字符不匹配时，通过前缀函数回退while(j>0&&s.charAt(i)!=s.charAt(j)){j=pi[j-1];// 回退到前一个可能匹配的位置}// 如果当前字符匹配，则增加匹配长度if(s.charAt(i)==s.charAt(j)){j++;}// 将当前字符的前缀函数值存入数组pi[i]=j;}returnpi;// 返回计算得到的前缀函数数组}