Cod sursa(job #552362)

Utilizator Sm3USmeu Rares Sm3U Data 12 martie 2011 10:10:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>

using namespace std;

char t[2000100];
char p[2000100];
int b[2000100];
int m;
int n;
int afis[1100];
int k;

void citire()
{
    gets(p);
    gets(t);
    n=strlen(t);
    m=strlen(p);
}

void creeazaB()
{
    int i=0;
    int j=-1;
    b[i]=j;
    while(i<m)
    {
        while(j>=0 && p[i]!=p[j]) j=b[j];
        i++;
        j++;
        b[i]=j;
    }
}
void cauta()
{
    int i=0;
    int j=0;
    while(i<n)
    {
        while(j>=0 && t[i]!=p[j]) j=b[j];
        i++;
        j++;
        if(j==m)
        {
            if(k<1000)
                afis[k++]=i-j;
            else
                k++;
            j=b[j];
        }
    }
}

void afisare()
{
    int K=k;
    if(k>1000)
        K=1000;
    printf("%d\n",k);
    for(int i=0;i<K;i++)
        printf("%d ",afis[i]);
}


int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    citire();
    creeazaB();
    cauta();
    afisare();
    return 0;
}