KMP法のテーブル作成プログラム

readme.md

KMP法のテーブル作成プログラム

• たぶんO(n)くらいで動く
• 証明もだいたい考えたので気が向いたら載せる

kmp.c

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

/*
lenが小さい時(len == 0,1)はオーバーフロー注意
skip[n] : n文字目で不一致の時何文字進めるか
u[n] : str[0..m-1] == str[n-m..n-1] を満たす最大のm(0<=m<n)
t[n] : str[0..m-1] == str[n-m..n-1] かつ s[m] != s[n]を満たす最大のm(0<=m<n)で、存在しなければ-1
*/
void kmp_table(char *str, int *t, int *u, int *skip, int len)
{
	u[0] = 0;
	u[1] = 0;
	t[0] = -1;
	skip[0] = 1;
	int m = 1, n;
	for(n=2;n<len;n++){
		while(str[m-1] != str[n-1]){
			if(m == 1){
				u[n] = 0;
				break;
			}
			m = u[m-1] + 1;
		}
		if(str[m-1] == str[n-1]){
			u[n] = m;
		}
		m = u[n] + 1;
	}
	for(n=1;n<len;n++){
		if(str[u[n]] == str[n]){
			t[n] = t[u[n]];
		}
		else{
			t[n] = u[n];
		}

		skip[n] = n - t[n];
	}
}

int main()
{
	char str[128];
	int u[128], t[128], skip[128];
	int len, i;
	scanf("%120s", str);
	len = strlen(str);
	kmp_table(str, t, u, skip, len);
	for(i=0;i<len;i++){
		printf("%c\t%d\t%d\t%d\n", str[i], t[i], u[i], skip[i]);
	}
	return 0;
}

Makefile

kmp: kmp.c
	gcc kmp.c -o kmp