小菜请教字符串匹配的高效算法

Question

ee区熟人多，我就不发se区了本贴探讨的关键词是算法效率，不仅仅是实现，呵呵。String a = "abcd,efg";
String b = ")(*&^%$#@![]{},./\;:'?<>";
要求是判断String a 里有没有哪个字符在String b里出现，效率越高越好。我自己技术菜，只能实现，效率极差，不好意思贴出来。还盼各位高手能贴出代码或给出思路，十分感谢！！另：网上找一个能判断是否包含这些特殊符号的正则式怎么这么难呢？找了很多都不对，知道的朋友也请告知，谢谢。

Answer 1

http://download.csdn.net/source/1951661
一本全面彻底讲解字符串查找算法的书。书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有进一步的参考文献。一本研究字符串查找算法不容错过的好书。 

Answer 2

Private Sub Form_Click()
x$ = "abcd,efg"
y$ = ")(*&^%$#@![]{},./\;:'? <>"
For i = 1 To Len(x)
 a = Mid(x, i, 1)
  If InStr(1, y, a) <> 0 Then
   Debug.Print "字符" & Mid(x, i, 1) & "存在于字符串b里"
  Else
   Debug.Print "字符" & Mid(x, i, 1) & "不存在于字符串b里"
  End If
Next
End Sub
不知道自己写得对不对，如果不对，请见谅！

Answer 3

楼主可以看看 JDK的源码里面的 indexOf的源码的实现。 自己再参考其他的算法修改一下。

Answer 4

请百度，bf以及kmp算法！我想字符串匹配效率目前没有超过kmp的吧…数据结构上的东西！楼主去看下吧…你的问题，遍历一遍a，内嵌kmp…效率应该高于正则

Answer 5

回1L：书是蝌蚪文的，不过还是谢谢。
回4L：这似乎就是最基本的遍历比对啊。
回6L：我本次考试就考的这本书，清华版严蔚敏的数据结构C版，可惜我基本没看书，书还在家躺着
回7L：谢谢指点，正在阅读中。
回8L：我这就去百度，原本以为此类事情正则要比写算法来的效率快，没想到还能比正则更快。
-----------------------------------
谢谢诸位的帮助，我今天继续研究

Answer 6

优酷上有严蔚敏讲授 KMP 的视频可以去看一下。

Answer 7

正则表达式只是方便使用。正则表达式在使用上看上去很简单，但是其内部的正则表达式引擎很复杂，我们从 Pattern 类的源代码行数数量就能得知。

Answer 8

String a = "abcd,efg";
String b = ")(*&^%$#@![]{},./\;:'? <>"; 如果确定是ASCII 没有汉字啥的，可以构造一个
byte[255] ba 的数组，对应 a里面的每一个字符，设置对应位为1，比如
ba['a'] = 1;
ba['b'] = 1;然后循环 b的每个字符，查找对应的ba 是不是为1

Answer 9

/**
 * 查找某些字符是否在另一个字符串里出现
 * 
 * @author Java人(java2000.net)
 */
public class Test {
  /**
   * @param args
   */
  public static void main(String[] args) {
    String a = "abcd,efg";
    String b = ")(*&^%$#@![]{},./\\;:'? <>";
    byte[] bb = new byte[256];
    char[] cs = b.toCharArray();
    for (char c : cs) {
      bb[c] = 1;
    }
    cs = a.toCharArray();
    for (char c : cs) {
      if (bb[c] == 1) {
        System.out.println(c);
      }
    }
  }
}

Answer 10

使用正则判断更简单    String pStr = "[)(*&^%$#@!\\[\\]{},./\\;:'? <>]";
    Pattern pChar = Pattern.compile(pStr, Pattern.DOTALL);
    System.out.println(pChar.matcher(a).find());在字符串 b 里前后加上[] 里面的[]替换为\\[ 和 \\]

Answer 11

哈哈。。好想法。。如果查单个字符的话，效率真的很高。。
用空间换时间。。老紫竹果然是CSDN上的老鸟哈。。哈哈
看来有时候学算法也不能学的太死了。。 

Answer 12

如果这样，那直接循环a的字符串长度然后String temp = a.substring(i,i+1);
然后在b里面b.indexOf(temp) > 0 不是更简单，何必再创建数组呢？

Answer 13

**
 * 查找某些字符是否在另一个字符串里出现
 * 
 * @author Java人(java2000.net)
 */
public class Test {
  /**
   * @param args
   */
  public static void main(String[] args) {
    String a = "abcd,efg";
    String b = ")(*&^%$#@![]{},./\\;:'? <>";
    byte[] bb = new byte[256];
    char[] cs = b.toCharArray();
    for (char c : cs) {
      bb[c] = 1;
    }
    cs = a.toCharArray();
    for (char c : cs) {
      if (bb[c] == 1) {
        System.out.println(c);
      }
    }
  }
}

Answer 14

谢谢大家的帮助。
String的indexOf源码经过分析后没能产生什么灵感。
------------------
方法1是我自己写的最基本的方法，百万次运行时间约1.8秒
方法2是老紫竹的方法，百万次运行时间约0.4秒
方法3是warison2008的思路，改进方法1而成，看其jdk源码可知，由于indexOf本身就要建立数组，其匹配方式也是比较基本的，因此效率不会好到哪去，百万次运行时间约2.5秒，比改进前还差。
方法4是老紫竹提供的正则式匹配法，百万次运行时间约3.3秒
------------------
粗略的测试结果显示，老紫竹的方法效率明显最高，而匹配正则式的方式如火龙果说的那样，效率真的不怎么样。
kmp算法也尝试了下，代码几乎看不出名堂，单步走也走了十几回，还是晕乎乎的，粗略运行了几遍，其效率还真的不错（百万次运行少于0.5秒）
------------------
测试代码：
import java.util.regex.Pattern;
/**
 * 测试字符串比对算法效率
 * @author dinghun8leech
 */
public class TestMatching {
/** TEMP_STRING 比对模板 */
private static final String TEMP_STRING = ",.;:\"'/?<>[]{}|\\+=-_()&*%^$#@!`~";
/** REG_STRING 匹配半角符号的正则 */
private static final String REG_STRING = "[)(*&^%$#@!\\[\\]{},./\\;:'?<>\\+\\~`=-_]";
/** TEST_STRING 测试字符串 */
private static final String TEST_STRING = "Your god will not save you!";
public static void main(String [] args) {
long beginTime = System.currentTimeMillis();
for (int i=0;i<1000000;i++) {
validateSign_1(TEST_STRING, TEMP_STRING);
}
System.out.println("算法1耗时：" + (System.currentTimeMillis() - beginTime) + "毫秒");

beginTime = System.currentTimeMillis();
for (int i=0;i<1000000;i++) {
validateSign_2(TEST_STRING, TEMP_STRING);
}
System.out.println("算法2耗时：" + (System.currentTimeMillis() - beginTime) + "毫秒");

beginTime = System.currentTimeMillis();
for (int i=0;i<1000000;i++) {
validateSign_3(TEST_STRING, REG_STRING);
}
System.out.println("算法3耗时：" + (System.currentTimeMillis() - beginTime) + "毫秒");

beginTime = System.currentTimeMillis();
for (int i=0;i<1000000;i++) {
validateSign_4(TEST_STRING, REG_STRING);
}
System.out.println("算法4耗时：" + (System.currentTimeMillis() - beginTime) + "毫秒");

beginTime = System.currentTimeMillis();
for (int i=0;i<1000000;i++) {
validateSign_5(TEST_STRING, REG_STRING);
}
System.out.println("算法5耗时：" + (System.currentTimeMillis() - beginTime) + "毫秒");
}
/**
 * 源自jdk1.6.0 String.indexOf方法的源码
 * @author Lee Boynton
 * @author Arthur van Hoff
 * @param char[] 比对模板的字符集合
 * @param int 比对模板字符串的偏移量
 * @param int 比对模板字符串的长度
 * @param char[] 查找关键字符集合
 * @param int 查找关键字符串的偏移量
 * @param int 查找关键字符串的长度
 * @param int 模板字符串的查找起点下标 
 * @return int 关键字符串位于模板字符串的起点下标
 */
static int indexOf_jdk(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first  = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++); if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
/**
 * jdk源码中String.indexOf方法的简化版，去除偏移量和起始比对下标
 * @author dinghun8leech
 * @param char[] 比对模板的字符集合
 * @param char[] 查找关键字符集合
 * @return int 关键字符串位于模板字符串的起点下标
 */
public static int indexOf_my(char [] source, char[] target) {
//如果原字符串和查找字符串长度有一个为0，或是查找字符串长度大于原字符串，直接返回-1
if (source.length < 1 || target.length < 1 || target.length > source.length) {
return -1;
}
char first  = target[0];//取查找字符串的第一个字符
int max = source.length - target.length;//取原字符串和查找字符串长度之差
for (int i=0; i<=max; i++) {//从原字符串集合0位开始遍历，直到集合剩余部分长度小于查找字符串长度为止
if (source[i] != first) {//当查找字符串首字符与当前下标的元字符串字符不符时将原字符串下标右移，直到匹配为止
while (++i <= max && source[i] != first);
}
if (i <= max) {//循环遍历查找字符串集合与原字符串集合首字符对应的一段字符，如果全部符合则返回起始下标，否则重复上一步
int j = i + 1;
int end = j + target.length - 1;
for (int k = 1; j < end && source[j] == target[k]; j++, k++);//questions 为何要加上关键字符串偏移量
if (j == end) {//当最后一个符合的下标正好为查找字符集合的长度+首字符下标时则表示此段字符完全匹配查找字符集合
return i;
}
}
}
return -1;//遍历完成后仍未找到任何匹配的字符段，返回-1
}
/**
 * 验证字符串1中是否不包含字符串2中的某个字符
 * 使用双循环遍历的基本方式进行
 * 1000000次运行耗时约为1800s
 * @author dinghun8leech
 * @param String 字符串1
 * @param String 字符串2
 * @return boolean 不包含返回true，否则返回false
 */
public static boolean validateSign_1(String source, String target) {
/*
if (source.length() < 1 || target.length() < 1) {
return true;
}*/
char sourceArray [] = source.toCharArray();
char targetArray [] = target.toCharArray();
for (char sourceElement : sourceArray) {
for (char targetElement : targetArray) {
if (sourceElement == targetElement) {
return false;
}
}
}
return true;
}
/**
 * 验证字符串1中是否不包含字符串2中的某个字符
 * 使用字符串2的char值为索引组建集合，并按字符串1中的char值进行查找的方式进行
 * 1000000次运行耗时约为410s，此方法还有优化余地
 * @author Java人(java2000.net)
 * @param String 字符串1
 * @param String 字符串2
 * @return boolean 不包含返回true，否则返回false
 */
public static boolean validateSign_2(String source, String target) {
    byte[] bb = new byte[256];
    char[] cs = target.toCharArray();
    for (char c : cs) {
     bb[c] = 1;
    }
    cs = source.toCharArray();
    for (char c : cs) {
     if (bb[c] == 1) {
     return false;
     }
    }
    return true;
}
/**
 * 验证字符串1中是否不包含字符串2中的某个字符
 * 方法1的改版，使用单循环遍历加indexOf的基本方式进行
 * 1000000次运行耗时约为2500s
 * @author warison2008
 * @param String 字符串1
 * @param String 字符串2
 * @return boolean 不包含返回true，否则返回false
 */
public static boolean validateSign_3(String source, String target) {
char sourceArray [] = source.toCharArray();
for (char sourceElement : sourceArray) {
if (target.indexOf(sourceElement) > -1) {
return false;
}
}
return true;
}
/**
 * 验证字符串中是否不包含给定正则中的符号
 * 使用正则表达式验证的方式进行
 * 1000000次运行耗时约为3300s
 * @author Java人(java2000.net)
 * @param String 需作判断的字符串
 * @param String 用于判断的正则
 * @return boolean 不包含返回true，否则返回false
 */
public static boolean validateSign_4(String source, String target) {
    Pattern pChar = Pattern.compile(target, Pattern.DOTALL);
    return !pChar.matcher(source).find();
}
/**
 * 验证字符串中是否不包含给定的匹配字符串
 * 使用kmp算法的方式行进
 * 1000000次运行耗时约为500s
 * @author dinghun8leech
 * @param String 需作判断的字符串
 * @param String 匹配字符串
 * @return boolean 不包含返回true，否则返回false
 */
public static boolean validateSign_5(String source, String target) {
int targetSize = target.length();
int sourceSize = source.length();
char[] targetArray = target.toCharArray();
char[] sourceArray = source.toCharArray();
   int[] P = parse(targetArray);
   int j=0;
   for (int i=0;i<sourceSize;i++) {
   while (j>0 && targetArray[j]!=sourceArray[i]) {
   j = P[j-1];
   }
   if (targetArray[j] == sourceArray[i]) {
   j++;
   }
   if (j == targetSize) {
   return false;
   }
   }
   return true;
}
/**
 * 解析匹配失败时子串回退的位置
 * @param char[] 待匹配子串的char数组
 * @return int[] 表述退回位置的数组
 */
private static int[] parse(char [] target) {
int[] parse = new int[target.length];
parse[0] = 0;
int j = 0;
for (int i=1; i<target.length; i++) {
while (j>0 && target[j]!=target[i]) {
j = parse[j];
}
if (target[j] == target[i]) {
j++;
}
parse[i] = j ;
}
return parse;
}
}
--------------------
没问题的话明天晚上结贴，然后啃严蔚敏那本C版数据结构去