Cod sursa(job #2028061)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 27 septembrie 2017 08:51:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

char a[2000005];
char b[2000005];
int  d[2000005];
int nrsol = -1, sol[1000];
int la, lb;

void precalc()
{
    int q = -1;
    d[0] = -1;
    for(int i = 1; i < la; i++)
    {
        while(q != -1 && a[q + 1] != a[i])
            q = d[q];
        if(a[q + 1] == a[i])
            q++;
        d[i] = q;
    }
}

void solve()
{
    precalc();
    int q = -1;
    for(int i = 0; i < lb; i++)
    {
        while(q != -1 && b[i] != a[q + 1])
            q = d[q];
        if(b[i] == a[q + 1])
            q++;
        if(q == la - 1)
        {
            ++nrsol;
            if(nrsol < 1000)
                sol[nrsol] = i - la + 1;
            q = d[q];
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", a, b);
    la = strlen(a);
    lb = strlen(b);
    solve();
    nrsol++;
    printf("%d\n", nrsol);
    int k = min(1000, nrsol);
    for(int i = 0; i < k; i++)
        printf("%d ", sol[i]);
    return 0;
}