Cod sursa(job #2289154)

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

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

int n,m,M,i,N,p[31][10100],k,poz,lung,j,nr,mini=INT_MAX,t;
char c[10100],s[10100],a[31][10100];


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

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

    while(j<=m){

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

    }






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

        k=-1;
        N=strlen(a[i]);
        p[i][0]=-1;
        for(j=1;j<N;j++){

            for(;k!=-1 && 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++){

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




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

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




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

            if(k==N-1)
            {

                if(j>poz){
                    if(j<mini){mini=j;}
                    poz=j;
                    lung=N;
                    nr++;
                    break;
                }
            }


        }

    }



    if(nr==t){
        g<<mini<<" "<<poz+lung-1;
    }
    else g<<-1;

    return 0;
}