Cod sursa(job #2323298)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 19 ianuarie 2019 01:59:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
#include <vector>
#define DIM 2000002

using namespace std;

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

char A[DIM], B[DIM];

int lgA, lgB, L;
int prefix[DIM];

vector<int> sol;

int main(int argc, const char * argv[]) {
    
    in>> A + 1 >> B + 1;
    lgA = strlen(A + 1);
    lgB = strlen(B + 1);
    
    //Precalculare functie prefix pentru A
    
    prefix[1] = 0;
    for(int i = 2; i <= lgA; ++ i){
        while(L != 0 && A[i] != A[L + 1])
            L = prefix[L];
        
        if(A[i] == A[L + 1])
            ++ L;
        
        prefix[i] = L;
        
    }
    
    
    //aplicare precalculare pe sirul mare
    L = 0;
    for(int i = 1; i <= lgB; ++ i){
        while(L != 0 && B[i] != A[L + 1])
            L = prefix[L];
        
        if(B[i] == A[L + 1])
            ++ L;
        if(L == lgA){
            sol.push_back(i - lgA);
            L = prefix[L];
        }
    }
    
    out<<sol.size()<<'\n';
    int size = min((int)sol.size(), 1000);
    for(int i = 0; i < size; ++ i)
        out<<sol[i]<<" ";
    
    return 0;
}