Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <algorithm>
- #include <string.h>
- #include <stack>
- #include <string>
- #include <set>
- #include <queue>
- #include <map>
- #include <math.h>
- using namespace std;
- #define f first
- #define s second
- #define mk make_pair
- #define pii pair<int,int>
- typedef long long ll;
- const int maxn = 200000 + 55;
- const int maxk = 20;
- const int prime = 1000000007;
- int n,m;
- char txt[maxn][maxk];
- ll start[maxn],end[maxn];
- inline ll gethash( char *pok, int sz ){
- ll ret = 0;
- for( ; sz ; sz -- , pok ++ )
- ret = ( ret * prime + *pok );
- return ret;
- }
- vector< pair<ll,char*> > lowtmp;
- void lower( ll *arr, int n ){
- for( int i = 0; i < n; ++i ){
- int lo = 0, hi = lowtmp.size()-1;
- int pos = -1;
- while( lo <= hi ){
- int mid = (lo+hi)>>1;
- if( lowtmp[mid].f >= arr[i] ) hi = mid - 1 , pos = mid;
- else lo = mid + 1;
- }
- arr[i] = pos;
- }
- }
- int cnte = 1;
- int head[maxn],point[maxn*2],nxt[maxn*2];
- int out[maxn];
- int in[maxn];
- void add_edge( int a, int b ){
- nxt[cnte] = head[a], point[cnte] = b, head[a] = cnte ++;
- out[a] ++;
- in[b] ++;
- }
- stack<int>euler;
- int curr[maxn];
- void dfs( int node ){
- while( curr[node] >= 1 ){
- int w = point[ curr[node] ];
- curr[node] = nxt[ curr[node] ];
- dfs( w );
- }
- euler.push( node );
- }
- char sol[maxn];
- bool done[maxn];
- int main(){
- scanf("%d%d",&n,&m);
- int len = n;
- n = n - m + 1;
- for( int i = 0; i < n; ++i ){
- scanf("%s",txt[i]);
- start[i] = gethash( txt[i], m - 1 );
- end[i] = gethash( txt[i] + 1 , m - 1 );
- lowtmp.push_back( mk( start[i] , &txt[i][0] ) );
- lowtmp.push_back( mk( end[i] , &txt[i][1] ) );
- }
- sort( lowtmp.begin(), lowtmp.end() );
- lower( start , n );
- lower( end , n );
- for( int i = 0; i < n; ++i )
- add_edge( start[i], end[i] );
- int s = 0;
- for( int i = 0; i < 2*n; ++i ){
- if( out[i] == in[i] + 1 ) s = i;
- curr[i] = head[i];
- }
- int sz = len - 1;
- dfs( s );
- int u;
- vector< int > us;
- while( euler.empty() == false ){
- u = euler.top();
- euler.pop();
- us.push_back(u);
- }
- for( int i = us.size()-1; i >= 0; --i ){
- u = us[i];
- sol[sz--] = *(lowtmp[u].s+m-2);
- }
- sol[len] = '\0';
- for( int i = 0; i < m-1; ++i )
- sol[i] = *(lowtmp[u].s+i);
- printf("%s\n",sol);
- return 0;
- }
Add Comment
Please, Sign In to add comment