Cod sursa(job #929600)

Utilizator andrettiAndretti Naiden andretti Data 27 martie 2013 09:48:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<vector>
#define maxn 2000005
using namespace std;

int m,n,nr;
char p[maxn],t[maxn];
int urm[maxn];
vector <int> sol;

void cit()
{
    char c;

    scanf("%c",&c);
    while(c!='\n')
    {
        p[++m]=c;
        scanf("%c",&c);
    }

    scanf("%c",&c);
    while(c!='\n')
    {
        t[++n]=c;
        scanf("%c",&c);
    }
}

void pref()
{
    int i,k=0;

    urm[1]=0;
    for(i=2;i<=m;i++)
    {
        while(k>0 && p[k+1]!=p[i]) k=urm[k];
        if(p[k+1]==p[i]) k++;
        urm[i]=k;
    }
}

void solve()
{
    int i,k=0;

    for(i=1;i<=n;i++)
    {
        while(k>0 && p[k+1]!=t[i]) k=urm[k];
        if(p[k+1]==t[i]) k++;
        if(k==m)
        {
            nr++;
            if(nr<=1000) sol.push_back(i-m);
            k=urm[k];
        }
    }
}

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

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    cit();
    pref();
    solve();
    afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}