游客 注册 | 登录
中文 | En

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

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB
字符串的子串定位称为模式匹配，模式匹配可以有多种方法。简单的算法可以使用两重嵌套循环，时间复杂度为母串与子串长度的乘积。而KMP算法相对来说在时间复杂度上要好得多，为母串与子串长度的和。但其算符比较难以理解。
在KMP算法中，使用到了一个next数组。这个数组就是在比较失配时母串指针不必回溯，而子串指针移动相应位置即可。我们给出书中next数组的算式表示以及算法，请你实现之。 

图1：next数组的算式表示


<img width="407" height="220" alt="" src="http://tk.hustoj.com:80/upload/pimg1750_2.jpg" />


图2：next数组的算法表示

题目输入

一个模式串，仅由英文小写字母组成。长度不大于100。

题目输出

输出模式串对应的移动数组next。每个整数后跟一个空格。

输入/输出样例

输入格式

abaabcac

输出格式

0 1 1 2 2 3 1 2

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;
}

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;
}

Java解答

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			testGetNext(cin);
		}
	}
	
	
	public static void testGetNext(Scanner cin)
	{
		
		String s = cin.nextLine();
		int next[] = new int[s.length()];
		getNext(s,next);
//		System.out.println(Arrays.toString(next));
		for( int i=0;i< s.length();i++)
		{
			System.out.print( (next[i] +1) +" " );
		}
		System.out.println();
	}

	public static int kmp(String s, String t) {
		int next[] = new int[t.length()];
		getNext(t, next);
		int n = kmpMatch(s,t,next);
		System.out.println(n);
		return n;
	}

	private static int kmpMatch(String s, String t, int[] next) {
		int j=0;
		int len = t.length();
		for(int i=0;i<s.length();i++)
		{
			if(s.charAt(i) == t.charAt(j)  )
			{
				if(j == len -1)
					return (i-len+2);
				j++;
			}
			else 
			{
				while(next[j] != -1)
				{
					if(s.charAt(i) == t.charAt(next[j]))
					{
						j= next[j] +1;
						break;
					}
					else j= next[j];
				}
			}
		}
		return 0;
	}

	private static void getNext(String t, int next[]) {

		next[0] = -1;
		for (int i = 1; i < t.length(); i++) {
			int k = next[i - 1];
			if ( k!= -1  && t.charAt(k) == t.charAt(i-1))
				next[i] = k + 1;
			else
			{
				next[i] =0;
				while( k!= -1 &&next[k]!= -1 )
				{
					k=next[k];
					if(t.charAt(k) == t.charAt(i-1))
					{
						next[i] = k+1;
					}
				}
				
			}
				
		}
	}
}
请先登陆