浏览 3797 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-10-22
下面是java中串匹配算法! 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 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; } public int indexOf(String str, int fromIndex) { return indexOf(value, offset, count, str.value, str.offset, str.count, fromIndex); }下面是数据结构中的算法: 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; } int[] T=new int[targetCount+1]; int c=1,t=0; while(c<targetCount){ if(t==0||target[c-1]==target[t-1]){ t++;c++; if(target[t-1]!=target[c-1])T[c]=t; else T[c]=T[t]; }else{ t=T[t]; } } c=targetOffset; t=sourceOffset; int max1=targetCount+targetOffset; int max2=sourceCount+sourceOffset; while(c<max1&&t<max2){ if(c==targetOffset||target[c]==source[t]){ c++;t++;} else { c=T[c]+targetOffset; } } if(c>=max1)return t-sourceOffset-targetCount; else return -1; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2009-10-22
如果source的长度是n,target的长度是m;则java库中的串匹配的复杂度是:
O(n*m);KMP的算法的复杂度约为O(n+m)!那位仁兄再改进改进!因为这是我 根据数据中的算法写的!有些地方不太简练! |
|
返回顶楼 | |