Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <math.h>
- #include <vector>
- #include <string>
- #include <utility>
- #include <stdio.h>
- #include <queue>
- #include <fstream>
- #include <functional>
- #include <cstdlib>
- #include <map>
- #include <set>
- #include <math.h>
- #include <string.h>
- #include <stdlib.h>
- using namespace std;
- typedef pair<int, int> ii ;
- typedef vector< ii > vii ;
- typedef vector<int> vi ;
- typedef vector<vi> vvi;
- typedef pair< int, string > is;
- #define pb push_back
- #define MAX_N 2000005
- int n, printable[MAX_N];
- int last[MAX_N];
- vector< ii > g[MAX_N];
- string sol,maxim;
- vector< string > sorted;
- bool cmp(const string &a, const string &b ){
- return a.length()>b.length();
- }
- void dfs(int n){
- for(int i=0;i<g[n].size();i++){
- if(!last[g[n][i].first]){
- sol.pb(char(g[n][i].second+'a'));
- dfs(g[n][i].first);
- }
- }
- for(int i=0;i<g[n].size();i++){
- if(last[g[n][i].first]){
- sol.pb(char(g[n][i].second+'a'));
- dfs(g[n][i].first);
- }
- }
- for(int i=0;i<printable[n];i++)
- sol.pb('P');
- sol.pb('-');
- }
- void dfsLast(int n, int pos){
- last[n] = 1;
- if(pos == maxim.size())
- return;
- for(int i=0;i<g[n].size();i++){
- if(char(g[n][i].second+'a') == maxim[pos] ){
- dfsLast(g[n][i].first,pos+1);
- break;
- }
- }
- }
- int main() {
- #ifdef EVAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- scanf("%d",&n);
- int maxNode = 0;
- for(int i=0;i<n;i++){
- char t[30]; scanf("%s",t);//cin>>t;
- string temp = t;
- if(temp.length() > maxim.length())
- maxim = temp;
- sorted.pb(temp);
- }
- //sort(sorted.begin(), sorted.end(), cmp);
- for(int i=0;i<n;i++){
- int nodeCurr = 0;
- for(int j=0;j<sorted[i].length();j++){
- int ind = -1 ;
- for(int k=0;k<g[nodeCurr].size();k++)
- if(g[nodeCurr][k].second == sorted[i][j]-'a'){
- ind = k;
- break;
- }
- if(ind == -1){
- g[nodeCurr].push_back(make_pair(++maxNode, sorted[i][j]-'a'));
- ind = g[nodeCurr].size()-1;
- }
- if(j == sorted[i].length() - 1)
- printable[maxNode]++;
- nodeCurr = g[nodeCurr][ind].first;
- }
- }
- /*for(int i=0;i<maxNode;i++){
- cout<<i<<": ";
- for(int j=0;j<g[i].size();j++)
- cout<<g[i][j].first<<" "<<char(g[i][j].second+'a')<<endl;
- }*/
- dfsLast(0,0);
- dfs(0);
- int k = sol.length()-1;
- while(sol[k] == '-')
- k--;
- printf("%d\n",k+1);
- for(int i=0;i<=k;i++)
- printf("%c\n",sol[i]);
- return 0;
- }
- //7 -1 2 -1 5 -2 3 -3 1 1 -1 -2 -1 -3 -4
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement