Cod sursa(job #929677)

Utilizator andrettiAndretti Naiden andretti Data 27 martie 2013 10:32:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>
#include<string.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()
{
    scanf("%s\n",p+1);
    scanf("%s",t+1);
    m=strlen(p+1);
    n=strlen(t+1);
}

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;
}