3280646_wa.cc

北大大牛代码 1240道题的原代码 超级权威

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

using namespace std;

int n, l, len;
char t[1001010], p[15];
int pai[15];
char tmp[1001010];

void pre()
{
	int k, q;

	pai[1] = 0;
	k = 0;
	for(q = 2; q <= len; q++)
	{
		while(k>0&&p[k+1]!=p[q])
			k = pai[k];
		if(p[k+1]==p[q])
			k++;
		pai[q] = k;
	}
}

int kmp()
{
	int i, q;

	q = 0;
	for(i = 1; i < n; i++)
	{
		while(q>0&&p[q+1]!=t[i])
			q = pai[q];
		if(p[q+1]==t[i])
			q++;
		if(q==len)
		{
			return i-len;
		}
	}
	return -1;
}

int min(int a,int b)
{
	return a < b ? a : b;
}

int main()
{
	int i, j, pos;
	char ch;

	freopen("A06.tst","r",stdin);
	scanf("%d%d",&n,&l);
	scanf("%s",t);
	reverse(t,t+n);
	for(i = 0; i < l; i++)
	{
		int ed;
		ed = min(13,n);
		for(j = 1; j <= ed; j++)
		{
			p[j] = t[j-1];
		}
		pos = -1;
		for(len = 13; len > 0; len--)
		{
			if(len >= n)
				continue;
			p[len+1] = '\0';
			pre();
			pos = kmp();
			if(pos!=-1)
			{
				ch = t[pos];
				break;
			}
		}
		if(pos==-1)
			ch = '0';
		putchar(ch);
		strcpy(tmp,t);
		t[0] = ch;
		t[1] = 0;
		strcat(t,tmp);
		n++;
	}
	putchar('\n');
	return 1;
}