Cod sursa(job #1604257)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 18 februarie 2016 08:57:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000007

using namespace std;
FILE *fin, *fout;
char A[NMAX], B[NMAX];
int pi[NMAX], ans[NMAX], ct, sze1, sze2;

void citire()
{
    scanf("%s%s", A + 1, B + 1);
}
void prefix()
{
    sze1 = strlen(A + 1);
    int k = 0;
    pi[1] = 0;
    for(int i = 2; i<= sze1; ++i)
    {
        while(A[k + 1] != A[i] && k) k = pi[k];
        if(A[k + 1] == A[i]) ++k;
        pi[i] = k;
    }
}
void KMP()
{
    sze2 = strlen(B + 1);
    int k = 0;
    for(int i = 1; i<= sze2; ++i)
    {
        while(k && B[i] != A[k+1]) k = pi[k];
        if(B[i] == A[k+1]) ++k;
        if(k == sze1)
        {
            ++ct;
            if(ct <= 1000)
            {
                ans[ct] = i - sze1;
            }
        }
    }
}
void afisare()
{
    printf("%d\n", ct);
    if(ct <= 1000) for(int i = 1; i<= ct; ++i) printf("%d ", ans[i]);
    else for(int i = 1; i<= 1000; ++i) printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    fin = freopen("strmatch.in", "r", stdin);
    fout = freopen("strmatch.out", "w", stdout);
    citire();
    prefix();
    KMP();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}