Cod sursa(job #2742788)

Utilizator ioan_bogioan bogdan ioan_bog Data 21 aprilie 2021 19:25:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstring>
#include <fstream>
using namespace std;
ifstream f("labirint.in");
ofstream g("labirint.out");
#define NumarElementeFiecareSir 2000004
char a[NumarElementeFiecareSir];///primul sir
char b[NumarElementeFiecareSir];///al doilea-->cel in care cautam sirul a
int v[NumarElementeFiecareSir];
int ElementeAfisare[1006];
int Length_first,Length_second;
int NumarElementeAfisat=1;
 int min(int a, int b){
    if(a<b) return a;
    return b;
}
 void read(char k[]){
    f>>k;
 }
void solve()
{
    v[1]=0;
    int prefixVal=0,i;
    for(i=2;i<=Length_first;i++)
    {
        while(prefixVal>0 && a[prefixVal+1]!=a[i])
            prefixVal=v[prefixVal];
        if(a[prefixVal+1]==a[i])
            prefixVal++;
        v[i]=prefixVal;
    }
    prefixVal=0;
    for(i=1;i<=Length_second;i++)
    {
        while(prefixVal>0 && a[prefixVal+1]!=b[i])
            prefixVal=v[prefixVal];
        if(a[prefixVal+1]==b[i])
            prefixVal++;

        if(prefixVal==Length_first)
        {
            if(NumarElementeAfisat<1000)
                ElementeAfisare[NumarElementeAfisat++]=i-prefixVal;
            else
                NumarElementeAfisat++;
        }
    }
}

int main()
{
    read(a);
    read(b);
    Length_first=strlen(a);
    Length_second=strlen(b);
    int i;
    for(i=Length_first;i>=1;i--)
        a[i]=a[i-1];
    for(i=Length_second;i>=1;i--)
        b[i]=b[i-1];

    solve();
    NumarElementeAfisat--;
    g<<NumarElementeAfisat<<"\n";
    for(i=1;i<=min(NumarElementeAfisat, 1001);i++)
        g<<ElementeAfisare[i]<<" ";
    return 0;
}