Cod sursa(job #2009629)

Utilizator HumikoPostu Alexandru Humiko Data 10 august 2017 11:50:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

char s[2000002];
long long counter, answer[1001];
int z[2000002];

void z_algorithm (int lungime, int n)
{
    int l, r;
    l = r = 1;
    for ( int i = 2; i<=n; ++i )
    {
        if ( i > r )
        {
            while ( z[i] + i <= n && s[z[i]+i] == s[z[i]+1])
                z[i]++;
            l = i;
            r = i + z[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 && s[z[i]+i] == s[z[i]+1])
                    z[i]++;
                l = i;
                r = i + z[i] - 1;
            }
        }
        if ( z[i] == lungime )
        {
            ++counter;
            if ( counter <= 1000 )
                answer[counter] = i - lungime - 2;
        }
    }
}

int main()
{
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);
    int n, i, len;
    cin>>(s+1);
    len = strlen(s+1);
    s[len+1] = '#';
    cin>>(s+len+2);
    n = strlen(s+1);
    z_algorithm(len, n);
    cout<<counter<<'\n';
    for ( int i = 1; i<=counter && i<=1000; ++i )
        cout<<answer[i]<<" ";
}