java 实现的Boyer-Moore(BM)算法
发布时间:2020-12-15 00:19:07 所属栏目:Java 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.ArrayList; import java.util.Map; public class Boy
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.ArrayList; import java.util.Map; public class BoyerMoore { public static List<Integer> match(String pattern,String text) { List<Integer> matches = new ArrayList<Integer>(); int m = text.length(); int n = pattern.length(); Map<Character,Integer> rightMostIndexes = preprocessForBadCharacterShift(pattern); int alignedAt = 0; while (alignedAt + (n - 1) < m) { for (int indexInPattern = n - 1; indexInPattern >= 0; indexInPattern--) { int indexInText = alignedAt + indexInPattern; char x = text.charAt(indexInText); char y = pattern.charAt(indexInPattern); if (indexInText >= m) break; if (x != y) { Integer r = rightMostIndexes.get(x); if (r == null) { alignedAt = indexInText + 1; } else { int shift = indexInText - (alignedAt + r); alignedAt += shift > 0 ? shift : 1; } break; } else if (indexInPattern == 0) { matches.add(alignedAt); alignedAt++; } } } return matches; } private static Map<Character,Integer> preprocessForBadCharacterShift( String pattern) { Map<Character,Integer> map = new HashMap<Character,Integer>(); for (int i = pattern.length() - 1; i >= 0; i--) { char c = pattern.charAt(i); if (!map.containsKey(c)) map.put(c,i); } return map; } public static void main(String[] args) { List<Integer> matches = match("ana","bananas"); for (Integer integer : matches) System.out.println("Match at: " + integer); System.out.println((matches.equals(Arrays.asList(1,3)) ? "OK" : "Failed")); } } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |