Sunday算法
判断字符串是否包含特定子串的算法,实现简单,运行高效。
import java.util.HashMap; import java.util.Map; public class Sunday { public static void main(String[] args) { System.out.println(contain("BBC ABCDAB ABCDABCDABDE","ABCDABD")); } public static int contain(String sourse,String target){ char[] sou = sourse.toCharArray(); char[] tar = target.toCharArray(); int S = sou.length; int T = tar.length; Map<Character,Integer> map = new HashMap<Character,Integer>(); for(int i =0;i<tar.length;i++) { map.put(tar[i],i); } int s =0; int t =0; while(s<=S-T) { t=0; while(sou[s+t]==tar[t]) { t++; if(t>T-1) { return s; } } if(map.containsKey(sou[s+T+1])) { s+=T+1-map.get(sou[s+T+1]); }else { s+=T+1; } } return -1; } }