Cod sursa(job #793750)

Utilizator Viva12Ferentz Sergiu Viva12 Data 3 octombrie 2012 22:20:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#define N 2000050
using namespace std;


int prefix[N];
char a[N];
char b[N];
int sol[1001];

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