3924936_tle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 67 行

#include <iostream>
#define N 1001001
using namespace std;

int n, l;
char arr[ N ];
int p[ N ];

void prepare(  )
{
	p[ n ] = n + 1;
	int j = n + 1;
	for ( int i = n - 1; i >= 1; i -- )
	{
		while ( j <= n && arr[ j - 1 ] != arr[ i ] ) j = p[ j ];
		if ( arr[ j - 1 ] == arr[ i ] ) j --;
		p[ i ] = j;
	}
}

int find( int t )
{
	for ( int i = n - t; i >= 1; i -- )
	if ( n - p[ i ] + 1 >= t ) return i;
	return 0;
}

void getans( )
{
	int k;
	bool flag;

	for ( int i = 1; i <= l; i ++ )
	{
		prepare( );
		flag = false;
		for ( int j = 13; j >= 1; j -- )
		{
			k = find( j );
			if ( k ) 
			{
				n ++;
				arr[ n ] = arr[ k + j ];
				flag = true;
				break;
			}
		}
		if ( ! flag ) 
		{
			n ++;
			arr[ n ] = '0';
		}
		cout << arr[ n ];
	}
}

int main( )
{
	cin >> n >> l;

	for ( int i = 1; i <= n; i ++ )
		cin >> arr[ i ];
	getans( );
	cout << endl;

	return 0;
}