Cod sursa(job #1233463)

Utilizator gerd13David Gergely gerd13 Data 25 septembrie 2014 15:19:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>


using namespace std ;

const int NMAX = 2000050 ;
const int shortNMAX = 1024 ;
const int INF = 0x3f3f3f3f ;

ifstream cin ("strmatch.in") ;
ofstream cout("strmatch.out") ;

int N, M;
char A[NMAX], B[NMAX] ;

int pi[NMAX], pos[shortNMAX] ;
//string A, B;

inline int min(int a, int b)
{
    if(a > b) return b ;
    else return a ;
}

inline int max(int a, int b)
{
    if(a < b) return b ;
    else return a ;
}


inline void prefix()
{
    int i, q = 0 ;

    for( i = 2, pi[1] = 0; i <= M ; ++ i)
    {
        while(q && A[q + 1] != A[i])

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

    }



}



int main()
{

    //memset(A, NULL, sizeof(A)) ;
    //memset(B, NULL, sizeof(B)) ;




    int i, q = 0, n = 0 ;
    cin >> A >> B ;

    //cout << A << '\n' << B << '\n' ;

    for(; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z') || (A[M] >= '0' && A[M] <= '9'); ++ M);
    for(; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z') || (B[N] >= '0' && B[N] <= '9'); ++ N);
    for(i = M ; i ; -- i) A[i] = A[i - 1];
    A[0] = ' ' ;
    for(i = N ; i ; -- i) B[i] = B[i - 1] ;
    B[0] = ' ' ;



    prefix() ;


    for(i = 1 ; i <= N ; ++ i)
    {
        while(q && A[q + 1] != B[i])
            q = pi[q] ;

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

        if(q == M)
        {
            q = pi[M] ;
            ++ n ;
            if(n <= 1000)
                pos[n] = i - M ;
        }
    }









    cout << n << '\n' ;

    for(int j = 1 ; j <= min(n, 1000) ; ++ j)
        cout << pos[i] << ' ' ;
    cout <<  '\n' ;



    cin.close() ;
    cout.close() ;
    return  0 ;
}