Cod sursa(job #2433860)

Utilizator ViAlexVisan Alexandru ViAlex Data 29 iunie 2019 15:28:17
Problema ADN Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<iostream>
#include<string>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");

string string_list[18];
int strings=0;
bool used[18] {false};

void read()
{
    in>>strings;
    for(int i=0; i<strings; i++)
    {
        in>>string_list[i];
    }

}
void compute_lsp(int*lsp_array,string to_compute)
{
    int i=1,l=0;
    lsp_array[0]=0;
    while(i<to_compute.length())
    {
        if(to_compute[i]==to_compute[l])
        {

            l++;
            lsp_array[i]=l;
            i++;
        }
        else
        {
            if(l!=0)
            {
                l=lsp_array[l-1];
            }
            else
            {
                lsp_array[i]=0;
                i++;
            }
        }
    }

}


string kmp(string main,string pattern)
{
    int lsp[pattern.length()];
    compute_lsp(lsp,pattern);
    int i=0,p=0;
    while(i<main.length())
    {
        if(main[i]==pattern[p])
        {
            i++;
            p++;
        }
        if(p==pattern.length())
        {
            p=lsp[p-1];
        }
        if(i<main.length() &&main[i]!=pattern[p])
        {
            if(p!=0)
            {
                p=lsp[p-1];
            }
            else
                i++;
        }

    }
    return main.substr(0,main.length()-p)+pattern;



}

string result="";

void backtrack(int current_depth,string merged)
{
    if(current_depth==strings)
    {
        if(result=="" || result.length()>merged.length())
            result=merged;
        return;
    }
    for(int i=0; i<strings; i++)
    {
        if(!used[i])
        {
            used[i]=true;
            backtrack(current_depth+1,kmp(merged,string_list[i]));
            used[i]=false;
        }
    }


}

int main()
{
    read();
    backtrack(0,"");
    out<<result;
    return 0;
}