Cod sursa(job #454879)

Utilizator voyagerSachelarie Bogdan voyager Data 12 mai 2010 19:05:36
Problema Substr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 17000
#define INF -1

typedef struct
{
	int half1, half2, val;
}
SUF;

using namespace std;

int size, cnt, k, log;
char text[NMAX], word[100];
SUF l[NMAX];
int arr[16][NMAX];

int sufCmp(const SUF& lVal, const SUF& rVal)
{
	return lVal.half1 != rVal.half1 ? lVal.half1 < rVal.half1 : lVal.half2 < rVal.half2;
}

void buildSuffixArray()
{
	for (int i = 0; i < size; ++i) arr[0][i] = text[i];

	for (int lg = 1, cnt = 1; log - lg + 1; ++lg, cnt <<= 1)
	{
		for (int i = 0; i < size; ++i)
			l[i].half1 = arr[lg - 1][i], l[i].half2 = i + cnt < size ? arr[lg - 1][i + cnt] : INF, l[i].val = i;
		sort(l, l + size, sufCmp);
		for (int i = 0; i < size; ++i)
			arr[lg][l[i].val] = (i != 0 && l[i].half1 == l[i - 1].half1 && l[i].half2 == l[i - 1].half2) ? arr[lg][l[i - 1].val] : i;
	}
}

int lcp(int i1, int i2)
{
	if (i1 == i2) return size - i1 + 1;

    int len = 0;
    for (cnt = log; cnt >= 0 && i1 < size && i2 < size; --cnt)
		if (!(arr[cnt][i1] - arr[cnt][i2]))
            len += (1 << cnt), i1 += (1 << cnt), i2 += (1 << cnt);
    return len;
}

int main()
{
	FILE *fin = fopen("substr.in", "r"), *fout = freopen("substr.out", "w", stdout);
	fscanf(fin, "%d %d\n", &size, &k);
	
	if (k == 1)
	{
		printf("%d\n", size);
		return 0;
	}

	while (1 << (log + 1) < size) ++log;
	fread(text, 1, size, fin);

	buildSuffixArray();

    int best = 0, len;

    for (int i = 0; i < size - k; ++i)
        if (len = lcp(l[i].val, l[i + k - 1].val)) best = max(best, len);

    printf("%d\n", best);

	return 0;
}