Cod sursa(job #2339677)

Utilizator fratele_meriusEnache-Stratulat Marius fratele_merius Data 9 februarie 2019 11:05:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[2000001],t[2000001];
int m,n,i,p[2000001],sol[1000],L,aparitii;
int main()
{
    fin>>s+1;
    fin>>t+1;

    n=strlen(s+1);
    m=strlen(t+1);

    L=0;

    for(i=2;i<=n;i++)
    {
        while(L and s[i]!=s[L+1])
            L=p[L];

        if(s[i]==s[L+1])
            L++;
        p[i]=L;
    }

    L=0;

    for(i=1;i<=m;i++)
    {
       while(L and t[i]!=s[L+1])
            L=p[L];

       if(t[i]==s[L+1])
            L++;

        if(L==n){
            aparitii++;
            if(aparitii<1000)
                sol[aparitii]=i-n;
        }
    }
    fout<<aparitii<<'\n';
    if(aparitii>1000)
        aparitii=1000;
    for(i=1;i<=aparitii;i++)
        fout<<sol[i]<<' ';
    return 0;
}