#include<iostream>
#include<fstream>
#include<string>
#include<vector>


using namespace std;

//НОД(а,б)
int gcd(int a, int b)
{
    while (b)

    {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}
// Запись из файла в строку
string write_text_to_string()
{
    ifstream text_file;

    text_file.open("Зашифрованный текст.txt", ios::in);

    string text, temp;
    text.clear();
    temp.clear();


    while (text_file)
    {
        text_file >> temp;
        text += temp;
        temp.clear();
    }

    text_file.close();

    return(text);
}
// Поиск n-грамам
void search_for_reps(string &text, int N, int min_repeat_count, int count_text_char)
{
    vector<string> N_gram;
    vector<int> repetitions;

    string substring_1, substring_2;
    substring_1.clear(), substring_2.clear();

    unsigned int repeat_count(0);

    for (unsigned int i = 0; (i < text.size() - N) || (i < count_text_char); i++)
    {
        substring_1 = text.substr(i, N);

        if (N_gram.size() != 0)
            for (unsigned int k = 0; k < N_gram.size(); k++)
                if (substring_1 == N_gram[k])
                {
                    substring_1.clear();
                    substring_1 = text.substr(i++, N);
                }


        for (unsigned int j = 0; j < text.size() - N; j++)
        {
            substring_2 = text.substr(j, N);

            if (substring_1 == substring_2)
                repeat_count++;

            substring_2.clear();
        }

        if (repeat_count > min_repeat_count)
        {
            N_gram.push_back(substring_1);
            repetitions.push_back(repeat_count);
            cout << substring_1 << "  " << repeat_count << endl << endl;
        }
        substring_1.clear();
        repeat_count = 0;

    }
}
// Индексы вхождения  n-грамам
vector<int> index_entries(string &mask, string &text)
{
    //cout<<"\n" << mask << " Входит в текст в позициях:\n ";

    vector<int> index_number;
    index_number.clear();


    for (unsigned int i = 0; i < text.size() - mask.size(); i++)

        if (mask == text.substr(i, mask.size()))
        {
            index_number.push_back(i);
            //cout << i << " \n";
        }


    return (index_number);
}
// Расчет дистанций между двумя n-грамами
vector<int> dist(string &mask, string &text)
{
    vector<int>index_number = index_entries(mask, text);
    vector<int> dist(index_number.size() - 1);

    for (unsigned int i = 0; i < dist.size(); i++)
    {
        dist[i] = index_number[i + 1] - index_number[i];
    }
    return(dist);
}
// НОД дистанций между двумя n-грамами
int gcd_dist(vector<int> &dist)
{
    int D=dist[0];
    for (unsigned int i = 1; i < dist.size(); i++)
    {
        D = gcd(dist[i],D);
    }

    return(D);
}
// Частотный анализ текста
void frequency_of_text_analysis(string &text)
{
    string alphabet = "АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЫЬЭЮЯ_";

    ofstream fout("Подсчет количества каждого символа алфавита в текте.txt");

    for (unsigned int i = 0; i < alphabet.size(); i++)
    {
        unsigned int counter = 0;

        for (unsigned int j = 0; j < text.size(); j++)
        {

            if (alphabet[i] == text[j])
                counter++;
        }


        fout << alphabet[i] << ": " << counter << endl;
    }

    fout.close();
}
//Вычисление дистанции между двумя n-грамами, с учетом возможного размера ключа
int gcd_dist_2(vector<int> &dist)
{
    ofstream fout("Длина ключа.txt", ios_base::app);

    fout << endl;
    fout << "По заданию длина ключа равна d, где 5 <=d<=12:\n";

    for (unsigned int i = 0; i < dist.size(); i++)
        for (unsigned int j = 1; j < dist.size()-i; j++)
        {
            if( (gcd(dist[i], dist[j + i])>4)&&(gcd(dist[i], dist[j + i])<13))
            fout << "НОД(" << dist[i] << ", " << dist[i + j] << ") = " << gcd(dist[i], dist[j + i])<< endl;
        }

    fout.close();
    return(0);
}
//Вычисление дистанции между двумя n-грамами, без учета возможного размера ключа
int gcd_dist_1(vector<int> &dist, string &mask)
{
    ofstream fout("Длина ключа.txt", ios_base::app);

    fout << endl;
    fout << "Исследуем расстояния между сочетаниями '"<<mask<<"'. Какие-то совпадения могут оказаться случайными, а какие-то содержат информацию\nо длине ключа. Вычислим НОД (попарно):\n";

    for (unsigned int i = 0; i < dist.size(); i++)
        for (unsigned int j = 1; j < dist.size() - i; j++)
            fout << "НОД(" << dist[i] << ", " << dist[i + j] << ") = " << gcd(dist[i], dist[j + i]) << endl;
    fout.close();
    return(0);
}
//Счетчик букв
void letter_counter(string &alphabet, string &text)
{
    ofstream fout("Частотный анализ текста записаннаго по столбцам.txt", ios_base::app);

    for (unsigned int i = 0; i < alphabet.size(); i++)
    {
        unsigned int counter = 0;

        for (unsigned int j = 0; j < text.size(); j++)
        {

            if (alphabet[i] == text[j])
                counter++;
        }

        fout << "\n";

        fout << alphabet[i] << ": " << counter << "; \n";
    }
    fout.close();
    return;
}

// Частотный анализ текста разбитого по N столбцам, где N - длина ключа
int frequency_analysis_on_the_columns(string &text, unsigned int n)
{
    vector<string> rows;

    while (text.size() > 0)
    {
        rows.push_back(text.substr(0, n));
        text = text.substr(n, text.size());

    }

    vector<string> cols(n);

    for (unsigned int i = 0; i < n; i++)
    {
        for (unsigned int j = 0; j < rows.size(); j++)
        {
            cols[i] += rows[j].at(i);
        }
    }

    string alphabet = "АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЫЬЭЮЯ_";

    ofstream fout("Частотный анализ текста записаннаго по столбцам.txt", ios_base::app);


    for (unsigned int i = 0; i < cols.size(); i++)
    {
        letter_counter(alphabet, cols[i]);

        fout << "Для столбца " << i + 1 << "\n____________________________________________________________________________________";

        fout << endl;
    }
    fout.close();
    return 0;
}
//Расшифровка текста
string decoding(string &text, string &key)
{
    string alphabet = "АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЫЬЭЮЯ_";

    vector<string> Vigenere_square(31);

    int row_table, column_table;
    string  new_text;
    char decoded_symbol;

    new_text.resize(text.size());

    for (int i = 0; i < 31; i++)
        for (int j = 0; j < 31; j++)
        {
            Vigenere_square[i].resize(31);
            Vigenere_square[i][j] = alphabet[(i + j)%31];
        }


    for(int i=0;i<key.size();i++)
        for(int j = i; j<text.size()-5;j=j+key.size())
        {
            row_table = alphabet.find(key[i]);
            column_table = Vigenere_square[row_table].find(text[j]);
            decoded_symbol = alphabet[column_table];
            new_text[j] = decoded_symbol;
        }

    ofstream fout("Расшифрованный текст.txt");
    fout << new_text;
    fout.close();


    // Вывод квадрата Вижинера в кнсоль
    for (int i = 0; i < 31; i++)
        for (int j = 0; j < 31; j++)
        {
            cout<< Vigenere_square[i][j]<< " ";
            if (j == 30) cout << "\n";
        }
    return  new_text;
}

void main()
{
    setlocale(LC_ALL, "RUS");

    string text = write_text_to_string();
    cout << text.size() << endl;


    while (text.size() % 9 != 0) // Дополненение текста символами, не входящими в алфавит, до размера кратного размеру ключа
    {                               //(Необходимо для коректной работы подпрограмм в которых происходит разбиение на строки)
        text = text + '!';
    }

    //search_for_reps(text, 4, 14, 1000);// Ищем сочитания по 4 символа, которые встречаются минимум 14 раз, расматриваем первую 1000 символов (сочетание должно встретится хотя бы раз)

    vector<int> a, b, c;
    a = dist(string("ЗИЖ_"), text);
    b = dist(string("ЯГЫЗ"), text);
    c = dist(string("НГРД"), text);

    ofstream fout("Длина ключа.txt");

    //fout << "НОД расстояний группы 'ЗИЖ_' равен " << gcd_dist(a) << ". Делаем вывод, что период кратен " << gcd_dist(a) << "." << endl;
    //fout << "НОД расстояний группы 'ЯГЫЗ' равен " << gcd_dist(b) << ". Делаем вывод, что период кратен " << gcd_dist(b) << "." << endl;
    //fout << "НОД расстояний группы 'ЯГЫЗ' равен " << gcd_dist(c) << ". Делаем вывод, что период кратен " << gcd_dist(c) << "." << endl;
    //fout << "Вероятней всего кодовое слово состоит из " << gcd(gcd(gcd_dist(a), gcd_dist(b)), gcd_dist(c)) << "символов." << endl;

    //fout << "\n"<<endl;

    gcd_dist_1(a, string("ЗИЖ_"));   gcd_dist_2(a);
    gcd_dist_1(b, string("ЯГЫЗ"));  gcd_dist_2(b);
    gcd_dist_1(c, string("НГРД"));  gcd_dist_2(c);


    fout.close();

    frequency_analysis_on_the_columns(text, 9); // 9 - длина ключа

    frequency_of_text_analysis(text);

    decoding (text, string("ЗАВЕЩАНИЕ"));

    system("pause");
}