java库中的String类中indexof(String s)应该改进为KMP算法

进来看数据结构中的串匹配算法！以为java中的算法应该是最优的！没想到是最简单的！
下面是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;
	}

评论

2 楼 busy12377 2012-06-26  

static int indexOf(char[] source,    
            char[] target,int fromIndex) {   
        int targetLength = target.length;
        int sourceLength = source.length;
        int[] next=new int[targetLength];   
       int i=0;
       next[0] = -1;
       int j = -1;
       while(i < targetLength-1){
    	   if(j == -1 || target[i] == target[j]){
    		   i++;j++;
    		   if(target[i]!=target[j]){
    			   next[i] = j;
    		   }else{
    			   next[i] = next[j];
    		   }
    	   }else{
    		   j = next[j];
    	   }
       }      
        j=-1;   
     	i=fromIndex;
        while(j<targetLength&&i<sourceLength){   
            if(j==-1||target[j]==source[i]){   
                i++;j++;
             }   
            else {   
                j=next[j];   
            }
        }   
        if(j>=targetLength)return i-targetLength;   
        else return -1;   
    }  
	static int indexOf(String src,String dest){
		return indexOf(src.toCharArray(),dest.toCharArray(),0);
	}
	static int indexOf(String src,String dest,int fromIndex){
		return indexOf(src.toCharArray(),dest.toCharArray(),fromIndex);
	}

1 楼 busy12377 2009-10-22  

如果source的长度是n，target的长度是m；则java库中的串匹配的复杂度是:
O(n*m);KMP的算法的复杂度约为O(n+m)！那位仁兄再改进改进！因为这是我
根据数据中的算法写的！有些地方不太简练！