Cod sursa(job #1414932)

Utilizator matei_cChristescu Matei matei_c Data 3 aprilie 2015 12:43:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

#define maxn 2000005

int na, nb ;
char A[maxn], B[maxn] ;

int pi[maxn], sol[1005] ;

void prefix()
{
    pi[1] = 0 ;

    int k = 0 ;

    for(int i = 2; i <= na; ++i)
    {
        while( k > 0 && A[k + 1] != A[i] )
            k = pi[k] ;

        if( A[k + 1] == A[i] )
            ++k ;

        pi[i] = k ;
    }
}

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

    scanf("%s\n", A + 1);
    na = strlen(A + 1) ;

    scanf("%s\n", B + 1);
    nb = strlen(B + 1) ;

    prefix() ;

    int q = 0 ;

    for(int i = 1; i <= nb; ++i)
    {
        while( q > 0 && A[q + 1] != B[i] )
            q = pi[q] ;

        if( A[q + 1] == B[i] )
            ++q ;

        if( q == na )
        {
            ++sol[0] ;

            if( sol[0] < 1001 )
                sol[ sol[0] ] = i - na ;
        }
    }

    printf("%d\n", sol[0]);

    for(int i = 1; i <= min( sol[0], 1000 ); ++i)
        printf("%d ", sol[i]);

	return 0 ;
}