Cod sursa(job #984859)

Utilizator gbi250Gabriela Moldovan gbi250 Data 15 august 2013 16:54:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>
#define SIZE  2000005
using namespace std;

char str[SIZE], pat[SIZE];
int i, j, k, str_len, pat_len, pi[SIZE], sol[1001];

inline void partial_match()
{
    int j=0;
    for(int i=2;i<=pat_len;++i)
    {
        while(j>0 && pat[i]!=pat[j+1])
            j=pi[j];
        if(pat[i]==pat[j+1])
            ++j;
        pi[i]=j;
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", pat+1, str+1);
    pat_len=strlen(pat+1);
    str_len=strlen(str+1);
    pat[0]=str[0]=' ';
    partial_match();
    for(i=1;i<=str_len;++i)
    {
        while(j>0 && pat[j+1]!=str[i])
            j=pi[j];
        if(pat[j+1]==str[i])
            ++j;
        if(j==pat_len)
        {
            if(k<1000)
                sol[++k]=i-pat_len;
            j=pi[j];
        }
    }
    printf("%d\n", k);
    for(i=1;i<=k;++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}