Cod sursa(job #984861)

Utilizator gbi250Gabriela Moldovan gbi250 Data 15 august 2013 16:56:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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)
        {
            ++k;
            if(k<1000)
                sol[k]=i-pat_len;
            j=pi[j];
        }
    }
    printf("%d\n", k);
    if(k>1000)
        k=1000;
    for(i=1;i<=k;++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}