История изменений
Исправление Siborgium, (текущая версия) :
Вкачусь и я, что ли. Кресты, требуются системные вызовы open, stat и mmap. Подсчитывается длина слова в байтах / 2, а не в символах. Обычно русские буквы занимают 2 байта, отсюда деление на 2. В остальном решение полностью честное.
#include <cassert>
#include <unistd.h>
#include <iostream>
#include <string_view>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <vector>
#include <algorithm>
int main() {
constexpr auto filename = "russian_nouns.txt";
int file = open(filename, O_RDONLY);
if (file < 0) {
perror("open failed: %s");
return EXIT_FAILURE;
}
struct stat statbuf;
if (fstat(file, &statbuf)) {
perror("fstat failed: %s");
return EXIT_FAILURE;
}
auto ptr = mmap(NULL, statbuf.st_size, PROT_READ, MAP_PRIVATE, file, 0);
if (ptr == MAP_FAILED) {
perror("mmap failed: %s");
return EXIT_FAILURE;
}
std::vector<const char*> newlines;
newlines.reserve(1024 * 1024);
{
auto begin = reinterpret_cast<char*>(ptr);
auto end = begin + statbuf.st_size;
newlines.push_back(begin - 1);
while (begin != end) {
if (*begin == '\n') {
newlines.push_back(begin);
}
++begin;
//begin = std::find(begin, end, '\n');
}
if (newlines.size() > 0 && *newlines.back() != '\n') {
++newlines.back();
}
}
std::size_t max_common_len{ 0 };
for (std::size_t i = 0; i + 1 < newlines.size(); ++i) {
std::string _( newlines[i] + 1, newlines[i + 1] - newlines[i] - 1 );
if (_.size() < max_common_len) {
continue;
}
std::string_view a{ _ };
for (std::size_t j = 0; j + 1 < newlines.size(); ++j) {
std::string_view b( newlines[j] + 1, newlines[j + 1] - newlines[j] - 1 );
if (newlines[i] == newlines[j] || b.size() < max_common_len) {
continue;
}
auto max = std::min(a.size(), b.size());
if (max <= max_common_len || a.ends_with(b) || b.starts_with(a)) {
continue;
}
auto a_ = a;
auto b_ = b;
a_.remove_prefix(a.size() - max);
b_.remove_suffix(b.size() - max);
while (max > max_common_len) {
if (a_.ends_with(b_)) {
max_common_len = max;
std::cout << (max / 2) << ' ' << a << " + " << b << " = " << a << b.substr(b_.size()) << '\n';
break;
}
b_.remove_suffix(1);
--max;
}
}
}
}
$ clang++ golf.cxx -std=c++2a -march=native -Wall -Wextra -Ofast
$ time ./a.out
4 абажур + ажурность = абажурность
5 абиогенез + генезис = абиогенезис
6 авансодатель + дательница = авансодательница
9 авансодержатель + держательница = авансодержательница
11 авансодержатель + содержательность = авансодержательность
13 воспроизводитель + производительность = воспроизводительность
real 0m5.169s
user 0m5.101s
sys 0m0.026s
Твой код компилировал с такими же флагами, получаю такой выхлоп:
$ clang++ -Ofast -march=native -std=c++2a kogrom.cxx
$ time ./a.out
417 прошло: 0 секунд, длина: 4, ажур - абажур-ажурность
878657 прошло: 0 секунд, длина: 5, генез - абиогенез-генезис
4009466 прошло: 1 секунд, длина: 6, датель - авансодатель-дательница
4061251 прошло: 1 секунд, длина: 9, держатель - авансодержатель-держательница
4093816 прошло: 1 секунд, длина: 11, содержатель - авансодержатель-содержательность
265157673 прошло: 5 секунд, длина: 13, производитель - воспроизводитель-производительность
Результат: 13, производитель - воспроизводитель-производительность
Полное время переборов: 29
real 0m28.378s
user 0m27.626s
sys 0m0.149s
Исходная версия Siborgium, :
Вкачусь и я, что ли. Кресты, требуются системные вызовы open, stat и mmap. Подсчитывается длина слова в байтах / 2, а не в символах. Обычно русские буквы занимают 2 байта, отсюда деление на 2. В остальном решение полностью честное.
#include <cassert>
#include <unistd.h>
#include <iostream>
#include <string_view>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <vector>
#include <algorithm>
int main() {
constexpr auto filename = "russian_nouns.txt";
int file = open(filename, O_RDONLY);
if (file < 0) {
perror("open failed: %s");
return EXIT_FAILURE;
}
struct stat statbuf;
if (fstat(file, &statbuf)) {
perror("fstat failed: %s");
return EXIT_FAILURE;
}
auto ptr = mmap(NULL, statbuf.st_size, PROT_READ, MAP_PRIVATE, file, 0);
if (ptr == MAP_FAILED) {
perror("mmap failed: %s");
return EXIT_FAILURE;
}
std::vector<const char*> newlines;
newlines.reserve(1024 * 1024);
{
auto begin = reinterpret_cast<char*>(ptr);
auto end = begin + statbuf.st_size;
newlines.push_back(begin - 1);
while (begin != end) {
if (*begin == '\n') {
newlines.push_back(begin);
}
++begin;
//begin = std::find(begin, end, '\n');
}
if (newlines.size() > 0 && *newlines.back() != '\n') {
++newlines.back();
}
}
std::size_t max_common_len{ 0 };
for (std::size_t i = 0; i + 1 < newlines.size(); ++i) {
std::string _( newlines[i] + 1, newlines[i + 1] - newlines[i] - 1 );
if (_.size() < max_common_len) {
continue;
}
std::string_view a{ _ };
for (std::size_t j = 0; j + 1 < newlines.size(); ++j) {
std::string_view b( newlines[j] + 1, newlines[j + 1] - newlines[j] - 1 );
if (newlines[i] == newlines[j] || b.size() < max_common_len) {
continue;
}
auto max = std::min(a.size(), b.size());
if (max <= max_common_len || a.ends_with(b) || b.starts_with(a)) {
continue;
}
auto a_ = a;
auto b_ = b;
a_.remove_prefix(a.size() - max);
b_.remove_suffix(b.size() - max);
while (max > max_common_len) {
if (a_.ends_with(b_)) {
max_common_len = max;
std::cout << (max / 2) << ' ' << a << " + " << b << " = " << a << b.substr(b_.size()) << '\n';
break;
}
b_.remove_suffix(1);
--max;
}
}
}
}
$ clang++ golf.cxx -std=c++2a -march=native -Wall -Wextra -Ofast
$ time ./a.out
4 абажур + ажурность = абажурность
5 абиогенез + генезис = абиогенезис
6 авансодатель + дательница = авансодательница
9 авансодержатель + держательница = авансодержательница
11 авансодержатель + содержательность = авансодержательность
13 воспроизводитель + производительность = воспроизводительность
real 0m5.169s
user 0m5.101s
sys 0m0.026s
Твой код компилировал с такими же флагами, получаю такой выхлоп:
$ clang++ -O2 -march=native -std=c++2a kogrom.cxx
$ time ./a.out
417 прошло: 0 секунд, длина: 4, ажур - абажур-ажурность
878657 прошло: 0 секунд, длина: 5, генез - абиогенез-генезис
4009466 прошло: 1 секунд, длина: 6, датель - авансодатель-дательница
4061251 прошло: 1 секунд, длина: 9, держатель - авансодержатель-держательница
4093816 прошло: 1 секунд, длина: 11, содержатель - авансодержатель-содержательность
265157673 прошло: 5 секунд, длина: 13, производитель - воспроизводитель-производительность
Результат: 13, производитель - воспроизводитель-производительность
Полное время переборов: 29
real 0m28.423s
user 0m28.122s
sys 0m0.027s