质疑String的匹配算法

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

String类提供了查找子串的方法,包括 indexOf(String str) ,indexOf(String str,int fromIndex),lastIndexOf(String str),lastIndexOf(String str,int fromIndex)。

我很奇怪为什么使用的是效率低下的普通算法,而没有使用高效的KMP算法,

我记得学数据结构的时候专门介绍了这个算法。下面是String的实现代码:

static int indexOf(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 i = sourceOffset + fromIndex;

int max = sourceOffset + (sourceCount - targetCount);

startSearchForFirstChar:

while (true) {

/* Look for first character. */

while (i <= max && source[i] != first) {

i++;

}

if (i > max) {

return -1;

}

/* Found first character, now look at the rest of v2 */

int j = i + 1;

int end = j + targetCount - 1;

int k = targetOffset + 1;

while (j < end) {

if (source[j++] != target[k++]) {

i++;

/* Look for str's first char again. */

continue startSearchForFirstChar;

}

}

return i - sourceOffset; /* Found whole string. */

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航