15章 Suffix配列を実装してみた

そろそろ終盤！
15章の問題に入る前にこの章の主題(?)を実装した.
文字列内の最長部分一致を見つける.
このアルゴリズムをSuffix配列と云うらしい.

qsortは不便だということを再確認(仕方ないけど).

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

void print_words(char ** ws, int N){
	for(int j=0; j<N; ++j){
		cout << "["<<j<<"]" << ws[j] << endl;
	}
}

int strcmp2(void const * const *x, void const * const *y){
	return strcmp((const char*)*x, (const char*)*y);
}

int common_length(char * sa, char * sb){
	int i;
	for(i=0; sa[i]!='\0'&&sb[i]!='\0'; i++){
		if(sa[i]!=sb[i]){
			break;
		}
	}
	return i;
}

void find_common_word(FILE * fp, int N){
	char * buff = new char[N];
	char ** suffix = new char*[N];

	char c;
	int i;
	for(i=0; (c=fgetc(fp))!=EOF && i<N-1; i++){ // #bug
		buff[i] = c;
		suffix[i] = &buff[i];
	}
	buff[i]='\0';
	suffix[i] = &buff[i];

	print_words(suffix, i);
	typedef int (*cmp_func)(const void*,const void*);
	qsort(suffix, i, sizeof(char*), (cmp_func)&strcmp2);
	print_words(suffix, i);

	int maxlen=0;
	int maxindex=-1;
	for(int k=0; k<i-1; k++){
		int len=common_length(suffix[k], suffix[k+1]);
		cout << suffix[k] << ":" << suffix[k+1] << " => " << len << endl;
		if(len>maxlen){
			maxlen=len;
			maxindex=k;
		}
	}
	cout << "maxlen=" << maxlen << endl;
	cout << "maxindex=" << maxindex << endl;
	cout << "string=[" << endl;
	cout << "\t[" << suffix[maxindex]   << "]" << endl;
	cout << "\t[" << suffix[maxindex+1] << "]" << endl;

	delete buff;
	delete suffix;
}

int main(){
	const int N = 100;
	FILE * fp=fopen("tmp.hpp", "r");
	if(!fp){
		goto ERROR_EXIT;
	}
	find_common_word(fp, N);
ERROR_EXIT:
	fclose(fp);
	return (0);
}

最初,コード中#bugのところの条件を間違えて

char buff[100]; // 始めはmain関数のスタック上に置いてた
for(i=0; (c=fgetc(fp))!=EOF && i<N  ; i++){ // bug :(
for(i=0; (c=fgetc(fp))!=EOF && i<N-1; i++){ // ok  :)

こんな感じに間違えてしまい,これをVC2008で実行すると
returnでmainから抜けるときに*1エラー吐いて落ちた….
これが入り組んだコードで発生したら…デバッグする自身がないorz

*1:多分スタック上の配列をdeleteしてる時