Cod sursa(job #1327992)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 27 ianuarie 2015 19:20:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int nmax = 2000000;
const int max_sol = 1000;

int n, m;

char a[nmax+5], b[nmax+5];
int pi[nmax+5];
vector <int> sol;

void prefix()
{
    pi[1] = 0;
    int q = 0;
    for(int i=2; i<=n; i++)
    {
        while(q && a[q+1] != a[i])
            q=pi[q];
        if(a[q+1] == a[i])
            q++;
        pi[i] = q;
    }
}

void prefix2()
{
    int q = 0;
    for(int i=1; i<=m; i++)
    {
        while(q && a[q+1] != b[i])
            q=pi[q];
        if(a[q+1] == b[i])
            q++;
        if(q == n)
        {
            q=pi[n];
            if(sol.size() < max_sol)
                sol.push_back(i-n+1);
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", a+1, b+1);

    n=strlen(a+1);
    m=strlen(b+1);

    prefix();
    prefix2();

    printf("%d\n", sol.size());
    for(int i=0; i<sol.size(); i++)
        printf("%d ", sol[i]);

    return 0;
}