苗火 Nicholas

[Data structures]String

2019-8-23 萧 写技术

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

#define MAX 255
typedef unsigned char SString[MAX+1];
int next[MAX];


/*
 * 0	:j == 1
 * k	:T[1...k-1] == T[j-(k-1)...j-1]
 * 1	:Others
 * */
void get_next(SString T, int next[])
{
	int i,j;
	i = 1;
	next[1] = 0;
	j = 0;
	while(i < T[0]){
		if(j == 0 || T[i] == T[j]){
			i++;
			j++;

#if 1			
			next[i] = j;
#else
			if(T[i] != T[j]){
				next[i] = j;
			}else{
				next[i] = next[j];
			}
#endif
		}else{
			j = next[j];
		}
	}
}

int Index_kmp(SString S, SString T, int pos)
{
	int i,j;
	i = pos;
	j = 1;
	while(i<=S[0] && j<=T[0]){
		if(j == 0 || S[i] == T[j]){
			i++;
			j++;
		}else{
			j = next[j];
		}
	}
	if(j>T[0]){
		return i-T[0];
	}else{
		return 0;
	}
}

void main()
{
	char *original_t = "abaabc";
	char *original_s = "aaaaabaabcbbbb";
	SString T,S;

	int i;

	printf("log.anycle.com\n\n");

	printf("Original data:\n");
	printf("S:%s\n", original_s);
	printf("T:%s\n", original_t);
	memcpy(T+1, original_t, strlen(original_t));
	memcpy(S+1, original_s, strlen(original_s));
	T[0] = strlen(original_t);
	S[0] = strlen(original_s);

	printf("Get next of T:\n");
	get_next(T, next);
	for(i=1; i<=T[0]; i++){
		printf(" %d", next[i]);
	}
	printf("\n");

	printf("Get position of T in S:\n");
	printf(" %d\n", Index_kmp(S, T, 0));
}

标签: Data Structures data_structures