Cod sursa(job #552372)

Utilizator 1994Barbulescu Daniel 1994 Data 12 martie 2011 10:22:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>
using namespace std;

char a[2000001];
char b[2000001];
int nr,k[1001],nr1;
int v[2000001];
int n,m;

void kmp()
{
    int i=0;
    int j=-1;
    v[i]=j;
    while (i<n)
    {
        while(j>=0 && a[j]!=a[i])
            j=v[j];
        i++;
        j++;
        v[i]=j;
    }
}

void cauta()
{
    int i=0;
    int j=0;
   // v[i]=j;
    while (i<m)
    {
        while (j>=0 && b[i]!=a[j])
            j=v[j];
        j++;
        i++;
        if (j==n)
        {
            if (nr1<1000)
                k[nr1]=i-j;
            nr1++;
            j=v[j];
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a);
    gets(b);
    n=strlen(a);
    m=strlen(b);
    kmp();
    cauta();
    printf("%d\n",nr1);
    if(nr1>1000)
        nr1=1000;
    for (int i=0;i<nr1;i++)
        printf("%d ",k[i]);
    return 0;
}