Cod sursa(job #929641)

Utilizator andrettiAndretti Naiden andretti Data 27 martie 2013 10:10:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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",nr);
    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();
    if(m<=n)
    {
      pref();
      solve();
      afis();
    }
    else printf("0\n");

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