Cod sursa(job #1123700)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 26 februarie 2014 09:43:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int key[2000005], na, nb, n;
char a[2000005], b[2000005];

vector<int> sol;

void debug_key()
{
    for(int i = 1; i <= na; i++)
        printf("%d ", key[i]);
    printf("\n");
}
void make_key()
{
    int k = 0;

    for(int i = 2; i <= na; i++)
    {
        while(k && a[i]!=a[k+1])
            k = key[k];
        if(a[i] == a[k+1])
            k++;
        key[i] = k;
    }
   // debug_key();
}

void solve()
{
    int k = 0;
    for(int i = 1; i <= nb; i++)
    {
        while(k && b[i]!=a[k+1])
            k = key[k];
        if(b[i] == a[k+1])
            k++;
        if(k == na)
        {
            n++;
            if(n < 1000)
                sol.push_back(i-na);
        }
    }
}

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

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s\n", a+1, b+1);
    na = strlen(a+1);
    nb = strlen(b+1);
    if(na > nb)
        printf("0\n");
    else
    {
        make_key();
        solve();
        afis();
    }

    return 0;
}