kmp

标准get_next（前缀函数）

void init(int m)
{
    memset(p, 0, sizeof(p));
    for(int i=1, k=0; i<m; i++)
    {
        while(k>0 && a[i]!=a[k]) k = p[k-1];
        if(a[i] == a[k]) k++;
        p[i] = k;
    }
}

get_next（有负一）

int Next[maxn];
void getnext(string s)
{
    int len = s.size();
    int k = -1;
    Next[0] = k;
    for (int i = 1; i < len; i++)
    {
        while (k > -1 && s[k + 1] != s[i])
            k = Next[k];
        if (s[k + 1] == s[i])
            k++;
        Next[i] = k;
    }
}

kmp

char a[maxn];
char b[maxn];
int ne[maxn];
/*
* ne[i]表示第0到i位的子串中 ，有长度为ne[i]的相同的前缀和后缀 
* input:        DABCDABD 
* output: next={00001231}
*/
void get_next(char a[],char b[])
{
	int j=0;
	int i=1;
	int lena=strlen(a);
	int lenb=strlen(b);
	while (i<lenb)
	{
		if (b[i]==b[j])
		{
			ne[i]=j+1;
			i++;
			j++;
		}
		else
		{
			if (j!=0)
			{
				j=ne[j-1];//
			}
			else
			{
				ne[i]=0;
				i++;
			}			
		}
	}	
} 
void kmp(char a[],char b[],vector<int> &position)//vector传引用
{
	int j=0;
	int i=0;
	int lena=strlen(a);
	int lenb=strlen(b);
	while (i<lena)
	{
		if (a[i]==b[j])
		{
			i++;
			j++;
		}
		else
		{
			if (j!=0)
			{
				j=ne[j-1];
			}	
			else
			{
				i++;
			}
		}
		if (j==lenb)
		{
			position.push_back(i-j+1);
//			printf("%d
",i-j+1);
		}
	}
}