Cod sursa(job #2119016)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 31 ianuarie 2018 15:35:11
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <cstring>

using namespace std;

char sir1[2000005], sir2[2000005];
int nr[2000005];

void citire(){
    fgets(sir1, 2000005, stdin);
    sir1[strlen(sir1) - 1] = 0;

    fgets(sir2, 2000005, stdin);
    sir2[strlen(sir2) - 1] = 0;
}

void construireInitiala(){
    int l = strlen(sir1);

    int nr1 = 0;

    for(int i = 1; i < l; i++){
        if(sir1[i] == sir1[nr1]){
            nr1++;
            nr[i] = nr1;
        }
        else{
            nr1 = nr[nr1 - 1];

            if(sir1[i] == sir1[nr1]){
                nr1++;
            }

            nr[i] = nr1;
        }
    }
}

int sol[1000000];
int nrSol = 0;

void solve(){
    int l = strlen(sir2);
    int ll = strlen(sir1);
    int p = 0;

    for(int i = 0; i < l; i++){
        if(sir2[i] == sir1[p]){
            p++;

            if(p == ll){
                sol[nrSol] = i + 1;
                nrSol++;

                p = nr[p - 1];
                i--;
            }
        }
        else{
            while(p > 0){
                p = nr[p - 1];

                if(sir2[i] == sir1[p]){
                    p++;
                    break;
                }
            }
        }
    }

    if(p == ll){
        sol[nrSol] = l;
        nrSol++;
    }

    printf("%d\n", nrSol);

    for(int i = 0; i < nrSol; i++){
        printf("%d ", sol[i] - ll);
    }
}

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

    citire();
    solve();

    return 0;
}

//aabaabaaa
//010123452