串的匹配模式

2019-04-13 16:32发布

站内文章 / 模拟电子
16077 0 1272
串的模式匹配 //3.3.1 朴素的模式匹配（Brute-Force）算法 public class BF { private static int count=0; //记载比较次数 //返回模式串pattern在目标串target中从begin开始的首次匹配位置，匹配失败时返回-1 public static int indexOf(String target, String pattern, int begin)java.lang.String字符串的查找、替换和删除子串操作。 public class DeleteString { //返回将target串中首个与pattern匹配的子串删除后的字符串 public static String deleteFirst(String target, String pattern) { int i=target.indexOf(pattern); if (i==-1) return target; return target.substring(0,i)+target.substring(i+pattern.length()); } //返回将target串中所有与pattern匹配的子串删除后的字符串 public static String deleteAll(String target, String pattern) { int i=target.indexOf(pattern); while (i!=-1) { target = target.substring(0,i)+target.substring(i+pattern.length()); i=target.indexOf(pattern,i); } return target; } public static void main(String args[]) { //图3.11，替换子串 // String target="ababdabcdabcabc", pattern="abc", replacement="xy"; //例3.3数据 String target="aaaa", pattern="a", replacement="ab"; //例3.4数据 System.out.println("""+target+"".indexOf(""+pattern+"")="+target.indexOf(pattern)); System.out.println("""+target+"".replaceFirst(""+pattern+"", ""+replacement+"")="+ target.replaceFirst(pattern,replacement)); System.out.println("""+target+"".replaceAll(""+pattern+"", ""+replacement+"")="+ target.replaceAll(pattern,replacement)); //图3.12，删除子串 System.out.println("deleteFirst(""+target+"", ""+pattern+"")="+deleteFirst(target, pattern)); System.out.println("deleteAll(""+target+"", ""+pattern+"")="+deleteAll(target, pattern)); } } /* 程序运行结果如下： //例3.3数据 "ababdabcdabcabc".indexOf("abc")=5 "ababdabcdabcabc".replaceFirst("abc", "xy")=ababdxydabcabc "ababdabcdabcabc".replaceAll("abc", "xy")=ababdxydxyxy deleteFirst("ababdabcdabcabc", "abc")=ababddabcabc deleteAll("ababdabcdabcabc", "abc")=ababdd //例3.4数据 "aaaa".indexOf("a")=0 "aaaa".replaceFirst("a", "ab")=abaaa "aaaa".replaceAll("a", "ab")=abababab deleteFirst("aaaa", "a")=aaa deleteAll("aaaa", "a")= */
int i=begin, j=0; //i、j分别为目标串和模式串当前字符的下标 count=0; while (i java.lang.StringBuffer字符串的替换和删除子串操作。 public class ReplaceStringBuffer { //将target串中首个与pattern匹配的子串替换成replacement，返回替换后的target串，改变target串 public static StringBuffer replaceFirst(StringBuffer target, String pattern, String replacement) { int i=target.indexOf(pattern); if(i!=-1) { target.delete(i, i+pattern.length()); //删除i～i+pattern.length()-1的子串 target.insert(i, replacement); //在第i个字符处插入replacement串 } return target; } //将target串中所有与pattern匹配的子串全部替换成replacement，返回替换后的target串，改变target串 public static StringBuffer replaceAll(StringBuffer target, String pattern, String replacement) { int i=target.indexOf(pattern); while (i!=-1) { target.delete(i, i+pattern.length()); target.insert(i, replacement); i=target.indexOf(pattern, i+replacement.length()); // i=target.indexOf(pattern, i+1); //错 } return target; } //删除target串中首个与pattern匹配的子串，返回删除后的target串，改变target串 public static StringBuffer deleteFirst(StringBuffer target, String pattern) { int i=target.indexOf(pattern); if(i!=-1) target.delete(i, i+pattern.length()); return target; } public static void main(String args[]) { StringBuffer target = new StringBuffer("ababdabcdabcabc"); //例3.3 数据 String pattern="abc", replacement="xy"; // StringBuffer target = new StringBuffer("aaaa"); //例3.4 数据 // String pattern="a", replacement="ab"; System.out.println("replaceFirst(""+target+"", ""+pattern+"", ""+replacement+"")="+ replaceFirst(target, pattern, replacement)); System.out.println("replaceAll(""+target+"", ""+pattern+"", ""+replacement+"")="+ replaceAll(target, pattern, replacement)); pattern=replacement; System.out.println("deleteFirst(""+target+"", ""+pattern+"")="+deleteFirst(target, pattern)); System.out.println("deleteAll(""+target+"", ""+pattern+"")="+deleteAll(target, pattern)); System.out.println("removeAll(""+target+"", ""+pattern+"")="+removeAll(target, pattern)); } //习题3，【例3.4】思考题 //删除target串中所有与pattern匹配的子串，返回删除后的target串，改变target串 public static StringBuffer deleteAll(StringBuffer target, String pattern) { int i=target.indexOf(pattern); while (i!=-1) { target.delete(i, i+pattern.length()); i=target.indexOf(pattern, i); } return target; } //删除target串中所有与pattern匹配的子串，返回删除后的target串，改变target串 //改进上述deleteAll()方法，对StringBuffer字符串删除所有匹配子串，字符一次移动到位 public static StringBuffer removeAll(StringBuffer target, String pattern) { int m=target.length(), n=pattern.length(); int i=target.indexOf(pattern), k=i; while (k!=-1) { int j=k+n; k=target.indexOf(pattern, j); while (k>0 && jKMP算法：public class KMP { private static int count=0; //记载比较次数 private static int[] next; //模式串pattern改进的next数组 private static int[] nextk; //模式串pattern未改进的next数组 //返回模式串pattern在目标串target中从begin开始的首次匹配位置，匹配失败时返回-1 public static int indexOf(String target, String pattern, int begin) { if (pattern.length()>0 && target.length()>=pattern.length()) { //当目标串比模式串长时进行比较 int i=begin, j=0; //i、j分别为目标串、模式串当前比较字符下标 count=0; nextk = getNextk(pattern); System.out.println("nextk[]: "+toString(nextk)); next = getNext(pattern); //返回模式串pattern改进的next数组 System.out.println("next[]: "+toString(next)); while (i

热门文章