Cod sursa(job #2480862)

Utilizator Vladv01Vlad Vladut Vladv01 Data 26 octombrie 2019 10:44:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;


const int maxv=2000001;

ifstream f("strmatch.in");
ofstream g("strmatch.out");


char a[maxv],b[maxv];
int n,m;
int p[maxv],nr,c[maxv];

void citire()
{

    f.getline(a+1,maxv);
    f.getline(b+1,maxv);
    a[0]='!';
    b[0]='!';
    n=strlen(a+1);
    m=strlen(b+1);
}

void potriv()
{
    p[1]=0;
    int j=0;
    for(int i=2;i<=n;i++)
    {

        if(a[i]==a[j+1])
            {
              j++;
            }
        while(a[i]!=a[j] && j!=0)
        {
            j=p[j];
        }
        p[i]=j;
    }

}

void caut()
{
    int j=0;
    for(int i=1;i<=m;i++)
    {
        while(j>0 && b[i]!=a[j+1])
        {
            j=p[j];
        }
        if(b[i]==a[j+1])
        {
            j++;
        }
        if(j==n)
        {
            nr++;
            if(nr<=1000)
               c[nr]=i-n;
        }
    }
}

int main()
{
    citire();
    potriv();
    caut();
    g<<nr<<"\n";
    if(nr>1000)
        nr=1000;
    for(int i=1;i<=nr;i++)
        g<<c[i]<<" ";
    return 0;
}