#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <map>
#include <queue>

using namespace std;

struct TRIE {
    map<char, TRIE> arcs;

    void add(char w[]) {
        if(w[0] != '\0') {
            arcs[w[0]].add(w+1);
		}
    }

    int check(char* w, int i = 0) {
        if(w[0] != '\0' && arcs.size() <= 2) {
            map<char, TRIE>::iterator it = arcs.find(w[0]);
            if (it != arcs.end())
               return arcs[w[0]].check(w+1, i+1);
            else return i;
        } else return i;
    }
};

int main() {
	const int MARGIN_OF_SIMILARITY = 3;

	int amount, maxC;
	cout << "Enter amount of files: ";
	cin >> amount;
	cout << "Enter max characters: ";
	cin >> maxC;

	int fileStartC = maxC/3, fileChangeC = maxC/3, fileEndC = maxC/3;

	TRIE start;
	priority_queue<string> names;

	for(int i = 0; i < amount; i++) {
		cout << "Enter " << i << ": ";
		string s;
		cin >> s;

		string r = s;
		reverse(r.begin(), r.end());//O(s.end() - s.begin())

		int similarStart = start.check((char *) s.data());//O(n)
		int similarEnd = start.check((char *) r.data());//O(n)

		string print;
		//if(similarStart < MARGIN_OF_SIMILARITY && similarEnd < MARGIN_OF_SIMILARITY) {
			start.add((char *) s.data());//O(n)
			start.add((char *) r.data());//O(n)
		//}

		names.push(s);
	}

	while(!names.empty()) {
		string n = names.top();
		cout << endl << "for " << n << endl;

		int similarStart = start.check((char *) n.data());//O(n)
		string t = n;
		reverse(t.begin(), t.end());
		cout << "reversed " << t << endl;
		int similarEnd = start.check((char *) t.data());//O(n)

		cout << "similar: start " << similarStart << " end " << similarEnd << endl;

		string print;
		if(similarStart < MARGIN_OF_SIMILARITY && similarEnd < MARGIN_OF_SIMILARITY) {
			if(n.length() > maxC) {
				cout << "length " << n.length() << endl;
				print = n.substr(0, maxC/2) + ".." +  n.substr(n.length()-maxC/2, n.length());
			} else {
				print = n;
			}
		} else {
			int shouldStart = similarStart > fileStartC? fileStartC:similarStart;
			int shouldEnd = similarEnd > fileEndC? fileEndC:similarEnd;
			cout << "shouldStart " << shouldStart << " similarStart " << similarStart << " similarEnd " << n.length()-similarEnd
					<< " shouldEnd " << n.length()-shouldEnd << endl;
			print = n.substr(0, shouldStart) + ".."
						+ n.substr(similarStart, (n.length()-similarEnd)-similarStart) + ".."
						+ n.substr(n.length()-shouldEnd, n.length());
		}

		cout << print << endl;
		names.pop();
	}
}