Cod sursa(job #793741)

Utilizator Viva12Ferentz Sergiu Viva12 Data 3 octombrie 2012 22:08:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <cstring>
#define N 2000000
using namespace std;


int prefix[N];
int sol[1001];
char a[N];
char b[N];
int k =0;
void pref(char s[])
{
    int length = strlen(s);
    int i = 0;
    int j = -1;

    prefix[0] = -1;
    while(i < length)
    {

    while( j >= 0 && a[i] != a[j])
    {
        j = prefix[j];
    }
    ++i;
    ++j;
    prefix[i] = j;


    }
}

void kmp()
{
    int length = strlen(a);
    int lengthB = strlen(b);
    int i =0;

    int j = 0;
    while (i < lengthB)
    {
        while(j>=0 && b[i] != a[j])
        {
            j = prefix[j];
        }
        i++;
        j++;

        if(j == length)
        {
            if(k < 1000)
            sol[k++] = i-j;
            else
            k++;
            j = prefix[j];
        }

    }
}

void afis()
{

    printf("%d\n",k);
    for(int i = 0; i < k ;i++)
    {
        printf("%d ",sol[i]);
    }
}
int main()
{

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&a,&b);
    pref(a);
    kmp();
    afis();
    return 0;
}