Cod sursa(job #2414223)

Utilizator Catalin_GriuGriu Catalin Catalin_Griu Data 24 aprilie 2019 12:58:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

int n, m;
char sir1[2000003];
char sir2[2000003];
int prefix[2000003];

void creare_prefix()
{
    int i=1, j=0;
    prefix[0]=0;
    while(i<=m)
    {
        if(sir1[i]==sir1[j])
        {
            prefix[i]=j+1;
            i++;
            j++;
        }
        else
        {
            while(j!=0 && sir1[i]!=sir1[j])
                j=prefix[j-1];
            if(sir1[i]==sir1[j])
                prefix[i]=j++ +1;
            i++;
        }
    }
}

int main()
{
    fin.getline(sir1, 2000003);
    fin.getline(sir2, 2000003);
    m = strlen(sir1)-1;
    n = strlen(sir2)-1;
    creare_prefix();
    //for(int i=0; i<=m; i++)
    //    fout<<prefix[i]<< ' ';
    int rez[1005];
    rez[0]=0;
    int j=0;
    int i =0;
    while(i<=n)
    {
        if(j<=m && sir1[j]==sir2[i])
        {
            i++;
            j++;
        }
        if(j==m+1)
        {
            rez[0]++;
            if(rez[0]<=1000)
                rez[rez[0]]=i-j;
            j = prefix[j-1];
        }
        else if(i<=n && sir1[j]!=sir2[i])
        {
            if(j>0)
                j = prefix[j-1];
            else
                i++;
        }
    }
    fout<<rez[0]<<'\n';
    for(int i =1; i<=rez[0] && i<=1000; i++)
        fout<<rez[i]<< ' ';
    return 0;
}