Cod sursa(job #1116797)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 22 februarie 2014 20:24:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
/* z-algorithm */

#include <fstream>
#include <cstring>
#include <cstdlib>
#include <vector>
#define NM 2000010


using namespace std;

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

char Pattern[NM], Text[NM];
int N, M, ANS;
int Z[NM], Match[NM];
vector<int> Poz;

void Read ()
{
    f >> (Pattern+1);
    N=strlen(Pattern+1);

    f >> (Text+1);
    M=strlen(Text+1);

    f.close();
}

void BuildZ ()
{
    int C=1, R=0;

    for (int i=2; i<=N; i++)
    {
        if (i<=R)
            Z[i]=min(Z[i-C+1], R-i+1);

        while (i+Z[i]<=N && Pattern[i+Z[i]]==Pattern[1+Z[i]])
            Z[i]++;

        if (i+Z[i]-1>R)
        {
            C=i;
            R=i+Z[i]-1;
        }
    }
}

void Solve ()
{
    int C=1, R=0;

    for (int i=1; i<=M; i++)
    {
        int lun=0;
        if (i<=R)
            lun=min(Z[i-C+1], R-i+1);

        while (1+lun<=N && i+lun<=M && Pattern[1+lun]==Text[i+lun])
            lun++;

        if (lun==N)
        {
            ANS++;
            if (ANS<=1000)
                Poz.push_back(i-1);
        }

        if (i+lun-1>R)
        {
            C=i;
            R=i+lun-1;
        }
    }
}

void Print ()
{
    g << ANS << '\n';
    for (size_t i=0; i<Poz.size(); i++)
        g << Poz[i] << ' ';

    g << '\n';
    g.close();
}

int main ()
{
    Read();
    BuildZ();
    Solve();
    Print();

    return 0;
}