Cod sursa(job #2432068)

Utilizator Garen456Paun Tudor Garen456 Data 21 iunie 2019 19:36:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[nmax],b[nmax];

int pi[nmax] , n , m;


vector < int > V;


void make_prefix()
{
    int k = 0;
    pi[1] = 0;
    ///fout << 0 << " ";
    for(int i = 2 ; i <= n; ++i)
    {
        while( k > 0 && a[ k + 1] != a[i] )
            k = pi[k];

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

        pi[i] = k;
        ///fout << pi[i] << " ";
    }
}

void KMP()
{
    int k = 0;

    for(int i  =  1 ; i <= m ; ++i)
        {
            while( k > 0 && a[k+1] != b[i] )
                k = pi[k];
            if( a[k+1] == b[i] )
                ++k;

            if( k  == n )
            {   k = pi[k];
                V.push_back( i - n );

            }
        }

}


int main()
{
    fin >> a + 1 ;
    fin >> b + 1 ;

    n = strlen(a + 1);
    m = strlen(b + 1);

    make_prefix();
    KMP();

    fout << V.size() << '\n';
    for(int i = 0 ; i < min((int)V.size(),1000) ; ++i)
        fout << V[i] << " ";

    return 0;
}