Cod sursa(job #2022888)

Utilizator HumikoPostu Alexandru Humiko Data 17 septembrie 2017 16:40:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstdio>
#include <string.h>

using namespace std;

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

char v[4000005];
long long counter, raspuns[1001];
int z[4000005];

void z_alg1(int n, int lungime)
{
    int l, r;
    l = r = 1;
    for ( int i = 2; i <= n; ++i )
    {
        if ( i > r )
        {
            while ( z[i] + i <= n && v[i+z[i]] == v[1+z[i]])
                ++z[i];
            l = i;
            r = z[i] + i - 1;
        }
        else
        {
            if ( i + z[i-l+1] - 1 < r)
                z[i] = z[i-l+1];
            else
            {
                z[i] = r - i;
                while ( z[i] + i <= n && v[i+z[i]] == v[1+z[i]])
                    ++z[i];
                l = i;
                r = z[i] + i - 1;
            }
        }
        if ( z[i] == lungime )
        {
            ++counter;
            if ( counter <= 1000)
                raspuns[counter] = i - lungime - 2;
        }
    }
}

int main()
{
    int n, i, len;
    fin>>(v+1);
    len = strlen (v+1);
    v[len+1] = '#';
    fin>>(v+len+2);
    n = strlen (v+1);
    z_alg1(n, len);
    fout<<counter<<'\n';
    for ( int i = 1; i <= counter && i <= 1000; ++i )
        fout<<raspuns[i]<<" ";
}