Cod sursa(job #1393899)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 19 martie 2015 20:45:23
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("potrivire.in");
ofstream g("potrivire.out");
int N,M,ind,Nr,Sol[10005],number;
vector <int> V[35];
int DP[35][10005],last,P[10005],Ind[10005],first=10005;
char Str[10005],B[10005],A[10005];
void Read()
{
    f>>N>>M;
    char ch;
    for(int i=1;i<=N;i++)
        f>>B[i];
    for(int i=1;i<=M;i++)
        f>>Str[i];
}

void Build_Prefixes()
{
    int i,q;
    P[1]=0;
    for(q=0,i=2;i<=ind;i++)
    {
        while(q&&A[q+1]!=A[i])
            q=P[q];
        if(A[q+1]==A[i])
            q++;
        P[i]=q;
    }
}
void KMP()
{
    int i,q=0;
    for(i=1;i<=N;i++)
    {
        while(q&&A[q+1]!=B[i])
            q=P[q];
        if(A[q+1]==B[i])
            q++;
        if(q==ind)
        {
            Nr++;
            Sol[Nr]=i-ind+1;
        }
    }
}
void precalcV()
{
    ind=0,number=0;
    for(int i=1;i<=M;i++)
    {
        if(Str[i]!='*')
            A[++ind]=Str[i];
        else
        {
            if(number==0 && ind==0)
                first=1;
            if(ind==0)
                continue;
            ++number;
            Ind[number]=ind;
            for(int i=1;i<=ind;i++)
                P[i]=0;
            Build_Prefixes();
            KMP();
            for(int i=1;i<=Nr;i++)
                V[number].push_back(Sol[i]);
            Nr=0;
            last=ind;
            ind=0;
        }
    }
    if(ind==0)
        return;
    ++number;
    for(int i=1;i<=ind;i++)
                P[i]=0;
            Build_Prefixes();
            KMP();
            for(int i=1;i<=Nr;i++)
                V[number].push_back(Sol[i]);
            Nr=0;
            last=ind;
        Ind[number]=ind;
}
void Solve()
{
    if(number==0)
    {
        g<<"1 1\n";
        return;
    }
    if(V[1].size()==0)
    {
        g<<-1<<"\n";
        return;
    }
    int last=V[1][0];
    bool ok=1;

    for(int i=2;i<=number;i++)
    {
        ok=0;
        for(int j=0;j<V[i].size();j++)
        {
            if(last+Ind[i-1]-1<V[i][j])
            {
                last=V[i][j];
                ok=1;
                break;
            }
        }
        if(ok==0)
            break;
    }
    if(ok==0)
    {
         g<<-1<<"\n";
         return;
    }

    g<<min(V[1][0],first)<<" "<<last+Ind[number]-1<<"\n";

}
int main()
{
    Read();
    precalcV();
    Solve();
    return 0;
}