重複見つけるやつ、ソート使ってO(nlogn)

ol_sort.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#define LINE 10000
#define ELEM 1000000
#include <chrono>

class Timer{
public:				
	Timer(){ restart(); }
public:
	void restart(){
		start_time = std::chrono::system_clock::now();
	}
	long long elapsed(){
		using namespace std::chrono;
		system_clock::time_point end_time = std::chrono::system_clock::now();
		auto dur = end_time - start_time;
		return duration_cast<microseconds> (dur).count();
	}
private:
	std::chrono::system_clock::time_point start_time;
};
void input(char* data,FILE* fp){
	char* p_data = data - 1;
	char* p_s;
	char s[128];
	int i;
	for (int j = 0; j < LINE; ++j){
		if (fgets(s, 128, fp) != NULL){
			p_s = s - 1;
			for (i = 0; i < 10; ++i){
				for (j = 0; j < 10; ++j){
					*(++p_data) = *(++p_s);
				}
				//this is 2ms faster than memcpy.
				++p_s;
			}
		}
	}
}
void algo_1(const char* data){
	Timer tm_algo;
	long long time_algo[10];
	char** data_sorted =new char*[ELEM] ;
	char* p = (char*)data;
	for (int i = 0; i < ELEM; ++i, ++p){
		data_sorted[i] =  p;
	}
	time_algo[0] = tm_algo.elapsed();
	std::sort(data_sorted, data_sorted + ELEM, [](const char* a, const char* b){
		int i = 0;
		while (*(a+i) == *(b+i)){
			++i;
		}
		return *(a+i) < *(b+i); 
	});		
	time_algo[1] = tm_algo.elapsed();
	int match_length_max = 0;
	int match_length = 0;
	std::vector<int> matched;
	for (int i = 0; i < ELEM - 1; ++i) {
		match_length = [](const char* a, const char* b) -> int{
			int j;
			for (j = 0; *(a + j) == *(b + j); ++j){}
			return j;
		}(data_sorted[i],data_sorted[i+1]);
		if (match_length_max < match_length){
			match_length_max = match_length;
			matched.clear();
			matched.push_back(i);
		}
		else if (match_length == match_length_max){
			matched.push_back(i);
		}
	}
	time_algo[2] = tm_algo.elapsed();
	for (int i = 0, n = matched.size(); i < n; ++i){
		int m = matched[i];
		char* c = data_sorted[m];
		for (int j = 0; j < match_length_max; ++j){
			std::cout << c[j];
		}
		std::cout << " pos:" << c - data << "," << data_sorted[i+1] - data << std::endl;
	}
	time_algo[3] = tm_algo.elapsed();

	for (int i = 0; i < 4; ++i){
		std::cout << i << ":" << time_algo[i] <<"us"<< std::endl;
	}
}
int main(void){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	char* data = new char[ELEM];
	long long time[10];
	int m = 0;
	Timer tm;
	input(data,stdin);
	//input(data, fp);
	time[0] = tm.elapsed();
	algo_1(data);	 
	time[1] = tm.elapsed();
	std::cout <<"INPUTFIN" << time[0] << "us" << std::endl;
	std::cout << "ALGOFIN" << time[1] << "us" << std::endl;
	return 0;
}

なんだっけこれ