Cod sursa(job #1998400)

Utilizator andreismara97Smarandoiu Andrei andreismara97 Data 7 iulie 2017 18:14:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

#define Nmax 2000005

char A[Nmax], B[Nmax];
int pi[Nmax], pos[Nmax], n = 0;

void getPrefix(int N)
{
    int i = 0;
    pi[0] = 0;
    for( int j = 1; j < N; j++ )
    {
        while( i && A[i] != A[j] )
            i = pi[i-1];
        if( A[i] == A[j] )
            i++;
        pi[j] = i;
    }

//    for( int j = 0; j < strlen(A); j++ )
//        out<<pi[j]<<'\n';
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);

    int i = 0, N = strlen(A) - 1, M = strlen(B) - 1;
    getPrefix(N);

    for( int j = 0; j < M; j++ )
    {
        while( i && A[i] != B[j])
            i = pi[i-1];
        if( A[i] == B[j] )
            i++;

        if( i == N )
        {
            i = pi[N-1];
            pos[++n] = j-N+1;
        }
    }
    printf("%d\n", n);
    for( int j = 1; j<=n && j<=1000; j++ )
        printf("%d ", pos[j]);
    printf("\n");
    return 0;
}