JOI2008本選 問題2＠C++(38)

ソートの比較時に一致長を調べるっていうこの方法は割と変な方法だけど、好み。

しかし苦労した。

ところで厳密にこの方法はOKなのだろうか・・・。

まあいいや。

/*
TASKNO: 2
LANG: C++
NAME: Masaki Hara J
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
int max_len=0;
class subseq
{
public:
	const char* base_str;
	int idx;
	const char* c_str;
	subseq(const char* base_str,int idx):base_str(base_str),idx(idx),c_str(&base_str[idx]) {}
	subseq():base_str(NULL),idx(0),c_str(NULL) {}
};

class ltstr
{
public:
	bool operator()(subseq ss1, subseq ss2) const
	{
		const char* s1=ss1.c_str;
		const char* s2=ss2.c_str;
		if(s1==s2)return 0;
		for(int i=0;;i++) {
			if(max_len<i && ss1.base_str!=ss2.base_str) {
				max_len=i;
				//printf("max_len=%d,i=%d,s1=%s,s2=%s\n",max_len,i,s1,s2);
			}
			if(s1[i]!=s2[i]) {
				return s1[i]<s2[i];
			}
			if(s1[i]=='\0') {
				return 0;
			}
		}
	}
};

using namespace std;

int main(int argc,char* argv[])
{
	FILE* in=fopen("input.txt","r");
	FILE* out=fopen("output.txt","w");
	char strA[4001];
	char strB[4001];
	printf("strA=%p,strB=%p\n",strA,strB);
	fscanf(in,"%s\n",strA);
	fscanf(in,"%s\n",strB);
	int strAlen=strlen(strA);
	int strBlen=strlen(strB);
	vector<subseq> subseqs(strAlen+strBlen);
	for(int i=0;i<strAlen;i++) {
		subseqs[i]=subseq(strA,i);
	}
	for(int i=0;i<strBlen;i++) {
		subseqs[i+strAlen]=subseq(strB,i);
	}
	ltstr lt_str;
	sort(subseqs.begin(),subseqs.end(),lt_str);
	fprintf(out,"%d\n",max_len);
	fclose(out);
	fclose(in);
	return 0;
}