Cod sursa(job #1829283)

Utilizator jurjstyleJurj Andrei jurjstyle Data 14 decembrie 2016 19:07:32
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
/*KMP
*/
#include <fstream>
#include <vector>
#include <cstring>

using namespace std ;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

char A[(int)(2e6+2)] , B[(int)(2e6+2)]; //memoreaza cele 2 siruri
int precomputing[(int)(2e6+2)] , M , N ; //memoreaza sirul prefixurilor si lungimile sirurilor citite
vector <int> Sol;//vectorul solutie


void prefix_computing()
{
    int poz = 2 ;//pt. unde calculam precomputing[poz]- denota pozitia curenta pt care calculam
    int cnd = 0 ;//desemneaza urmatorul caracter a subisurului candidat curent
    precomputing[0] = -1 , precomputing[1] = 0; //valori initiale
    while ( poz < M )
    {
        if ( A[poz-1] == A[cnd] ) //daca substringul continua
            precomputing[poz++] = ++cnd;
        else if ( cnd > 0 ) //daca substringul nu continua dar "avem unde sa ne intoarcem"
            cnd = precomputing[cnd] ;
        else // nu mai avem nici de intors ( lipsa de candidati ) adica cnd = 0
            precomputing[poz++] = 0;
    }
}
void KMP_search()
{
    int i = 0;//pozitia curenta in A
    int j = 0;//pozitia curenta in B
    while ( i + j < N ) //cat timp avem sanse de un subsir care sa fie chiar pana in capat ( ultima varianta)
    {
        if ( A[i] == B[j + i] )
        {
            if ( i == M - 1 )
            {
                if ( Sol.size() < 1000 )
                    Sol.push_back(j) ;
                j = j + i - precomputing[i] , i = precomputing[i] ;
            }
            else
                ++i ;
        }
        else if ( precomputing[i] >= 0 )
                j = j + i - precomputing[i] , i = precomputing[i] ;
            else
                ++j , i = 0;
    }

}

int main ()
{
    f.getline ( A , 2e6+1 );
    M = strlen(A) ;
    f.getline ( B , 2e6+1 );
    N = strlen(B) ;
    prefix_computing();
    KMP_search();
    g << Sol.size() << "\n" ;
    for ( const int & x : Sol )
        g << x << " ";
}