12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697import java.util.*;import java.io.*;//复习spfapublic class Main{ static int n,m,k; static int N=(int)(2e5+10); public static void main(String[] args) { n=in.nextInt(); m=in.nextInt(); //k=in.nextInt(); for(int i=1;i<=m;i++) { int a=in.nextInt(); int b=in.nextInt(); int c=in.nextInt(); a ...
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899import java.util.*;import java.io.*;//dijpublic class Main { static int N=(int)(1e5+10); public static void main(String args[]) { int n=in.nextInt(); int m=in.nextInt(); ArrayList<int[]> node[]=new ArrayList[N]; for(int i=1;i<=m;i++) { int u=in.nextInt(); int v=in.nextInt(); i ...
KMP算法
KMP核心思路性质：当前字符的前缀长度一定小于等于当前长度,next[i]<=i思路：当前字符的前缀长度初始化为前一个字符的前缀长度(前一个字符已经验证了当前字符以前的前缀)匹配这个前缀长度的前缀末端下一个元素与当前元素是否相等，如果相等，长度加一，如果不等，获取前缀末端的前缀长度继续匹配。
如图
1234567891011121314151617//核心代码static void KMP(String str){ int len=0; next[1]=0; for(int i=2;i<str.length();i++){ while(len>0&&str.charAt(i)!=str.charAt(len+1)){ len=next[len]; } if(str.charAt(i)==str.charAt(len+1)){ len++; } ...
algorithm
未读Manacher回文串高效算法
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394import java.util.*;import java.io.*;//Manacher算法public class Main{ public static void main(String args[]) { int n=in.nextInt();//n长度的字符串 String str=in.next();//字符串 StringBuilder sb=new StringBuilder();//可修改字符串 for(int i=0;i<str.length();i++) {//变成#字符串#格式去除奇偶性 sb.append("#&quo ...
字符串单哈希，单哈希有可能被卡哈希值
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import java.util.*;import java.io.*;//字符串单哈希public class Main { static int mod=998244353;//哈希模数 static int p=131;//哈希倍率 static String str; public static void main(String args[]) { int n=in.nextInt();//长度n的字符串 int q=in.nextInt();//q次询问 str=" "+in.next();//从1开始的字符串 init();//初始化字符串哈希 while(q-->0) & ...
algorithm
未读线段树，支持单点修改，区间查询
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102import java.util.*;import java.io.*;//线段树(单点修改，区间查询)public class Main { static int a[]; public static void main(String args[]) { a=new int[N]; for(int i=1;i<=100;i++) { a[i]=i; } build(1,1,100);//建树区间1-100 out.println(query(1,1,100));//区间1-100的sum和 out.fl ...
