个人技术分享

c++代码

#include<iostream>
#include<string>
#include <vector>
using namespace std;
void getNext(string& sub, int* next)
{
	
	int lenSub = sub.length();
	//next = new int[lenSub];
	//next.resize(lenSub);
	next[0] = -1;
	if (lenSub > 1)
		next[1] = 0;
	int i = 2;//当前i下标
	int k = 0;//前一项的k
	while (i<lenSub)
	{
		if (k == -1 || sub[i-1] == sub[k])//
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
			k = next[k];
	}
}
int kmp(string str, string sub, int pos)
{
	if (str.empty() || sub.empty()) return -1;
	int lenStr = str.length();
	int lenSub = sub.length();
	if (pos < 0 || pos >= lenStr) return -1;
	int i = 0, j = 0;
	int* next = new int[lenSub];
	//vector<int> next;
	getNext(sub, next);
	while (i < lenStr && j < lenSub)
	{
		if (j==-1||str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= lenSub) return i - j;
	else return -1;
}
int main()
{
	int ret = kmp("abcaaadc", "caaa", 0);
	cout << ret << endl;//2
	return 0;
}

java代码 

import java.util.*;
/*
    str:主串
    sub:子串
    pos:从主串的pos位置开始查找
    return:返回子串在主串中位置的下标
 */
public class Main {
    public static int kmp(String str,String sub,int pos){
        int lenStr=str.length();
        int lenSub=sub.length();
        if(str==null||sub==null) return -1;
        if (lenStr==0||lenSub==0) return -1;
        int[] next=new int[lenSub];
        getNext(sub,next);
        if(pos<0||pos>=lenStr) return -1;
        int i=pos,j=0;
        while (i<lenStr&&j<lenSub)
        {
            if(j==-1||str.charAt(i)==sub.charAt(j))
            {
                ++i;
                ++j;
            }
            else
            {
                j=next[j];
            }
        }
        if(j>=lenSub) return  i-j;
        else return  -1;
    }
    public static void getNext(String sub,int[] next)
    {
        int lenSub=sub.length();
        next[0]=-1;
        next[1]=0;
        int k=0;
        int i=2;
        while(i<lenSub)
        {
            if(k==-1||sub.charAt(i-1)==sub.charAt(k)){
                next[i]=k+1;
                i++;
                k++;
            }
            else {
                k=next[k];
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(kmp("abca" +"aaaabcda","caa",0));
       // System.out.println("Hello world!");
    }
}