1351 - 算法4-7：KMP算法中的模式串移动数组

abaabcac

0 1 1 2 2 3 1 2 

Hint

提示：
数据结构与以前相同，只用字符数组即可，只要调用上述函数即可。
总结：
KMP算法在字符串模式匹配算法中比较高效，具体KMP算法将在以后介绍。
  参考代码：
http://www.csbiji.com/thread-39884-1-1.html

Solution C

#include<stdio.h>
#include<string.h>
#define S 10000
#define T 100
int next[T]={0};
void get_next(char t[],int next[])
{
    int i=0,j=-1;
    while(t[i+1]!='\0')
    {
        if(j==-1||t[i]==t[j])
        {
            ++i;++j;
            next[i]=j+1;
        }
        else
            j=next[j]-1;
    }
}
void get_nextval(char t[],int next[])
{
    int i=0,j=-1;
    while(t[i+1]!='\0')
    {
        if(j==-1||t[i]==t[j])
        {
            ++i;++j;
            if(t[i]!=t[j])
                next[i]=j+1;
            else
                next[i]=next[j];
        }
        else
            j=next[j]-1;
    }
}
int kmp(char s[],char t[],int pos)
{
    int i=pos-1,j=0,a=strlen(s),b=strlen(t);
    while(i<=a-1&&j<=b-1)
    {
        if(j==-1||s[i]==t[j])
        {++i;++j;}
        else
            j=next[j]-1;
    }
    if(j==b)
        return i-j+1;
    else
        return 0;
}
int main()
{
  int i,l;  char s[S],t[T];
    gets(t);
    get_next(t,next);
    //get_nextval(t,next);
    l=strlen(t);
  for(i=0;i<=l-1;i++)
  printf("%d ",next[i]);
  printf("\n");  
  return 0;
}

Solution C++

#include <stdio.h>
#include <string.h>

#define MAXSTRLEN 100
typedef char SString[MAXSTRLEN+2];

void InputString(SString &str) {
	// 读取字符串
	scanf("%s", str + 1); // 首先用scanf读取字符串
	str[0] = strlen(str + 1); // 求出字符串的长度并保存在str[0]中
}

void get_next(SString T, int *next) { // 算法4.7
	int i = 1;
	next[1] = 0;
	int j = 0;
	while (i < T[0]) {
		if (j == 0 || T[i] == T[j]) {
			++i;
			++j;
			next[i] = j;
		} else
			j = next[j];
	}
}

int main(){
	SString str;
	int next[MAXSTRLEN+2];
	int i;
	InputString(str);
	get_next(str, next);
	for(i=1; i<=str[0]; i++){
		printf("%d ",next[i]);
	}

	return 0;
}