Cod sursa(job #2289397)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 24 noiembrie 2018 15:33:17
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("potrivire.in");
ofstream g("potrivire.out");

long long n,m,M,NR,i,N,p[35][10100],k,poz,lung,j,nr,mini,t;
char c[10100],s[10100],a[35][10100];


int main()
{
    f>>n>>m;
    f>>(c+1);
    f>>s;

    t=0;
    M=0;
    j=0;


    while(s[j]=='*')
    {
        NR++;
        j++;
    }

    while(j<=m)
    {

        if('a'<=s[j]&&s[j]<='z' || 'A'<=s[j]&&s[j]<='Z')
        {

            t++;
            while('a'<=s[j]&&s[j]<='z' || 'A'<=s[j]&&s[j]<='Z')
            {
                M++;
                a[t][0]++;
                a[t][a[t][0]]=s[j];
                j++;
            }
            a[t][a[t][0]+1]=='\0';
        }
        else
        {
            j++;
        }

    }






    for(i=1; i<=t; i++)
    {

        k=0;
        N=a[i][0];

        for(j=2; j<=N; j++)
        {

            for(;k!=0 && a[i][k+1]!=a[i][j];)k=p[i][k];
            if(a[i][k+1]==a[i][j])k++;
            p[i][j]=k;

        }

    }


    /*for(i=1;i<=t;i++){
    {1}
        N=strlen(a[i]);
        for(j=0;j<N;j++)
            g<<p[i][j]<<" ";
        g<<'\n';
    }*/




    poz=0;
    for(i=1; i<=t; i++)
    {

        k=0;
        N=a[i][0];
        for(j=poz+1; j<=n; j++)
        {

            for(;k!=0 && a[i][k+1]!=c[j];)k=p[i][k];
            if(a[i][k+1]==c[j])k++;

            if(k==N)
            {
                //g<<c[j]<<'\n';
                if(poz==0)mini=j;
                poz=j;
                nr++;
                j=n+1;
                break;

            }


        }

    }



    if(nr==t)
    {
        if(NR>=1)
            g<<1<<" "<<poz;
        else
            g<<mini-a[1][0]+1-NR*30<<" "<<poz;
    }
    else g<<-1;

    return 0;
}