Cod sursa(job #1618678)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 27 februarie 2016 22:27:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>

using namespace std;

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

vector <long long> Sol;
long long L[2000005];
long long n, m;
char A[2000005], B[2000005], Aux[2000005];

void citire()
{
    f.getline(Aux, 2000005);
    A[0] = '*';
    strcat(A, Aux);
    f.getline(Aux, 2000005);
    B[0] = '*';
    strcat(B, Aux);
    n = strlen(A);
    m = strlen(B);
}

void precalc()
{
    long long prev, i;
    for(i=2; i<n; i++){
        prev = L[i-1];
        while(prev && A[i] != A[prev + 1])
            prev = L[prev];

        if(A[i] == A[prev + 1])
            L[i] = prev + 1;
    }
}

void KMP()
{
    long long potri = 0, i;
    for(i=1; i<m; i++){
        while(potri && B[i] != A[potri + 1]){
            potri = L[potri];
        }

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

        if(potri == (n-1))
            Sol.push_back(i - n + 1);
    }

    g<<Sol.size()<<"\n";
    for(i=0; i<Sol.size() && i<1000; i++)
        g<<Sol[i]<<" ";
    g<<"\n";
}

int main()
{
    citire();
    precalc();
    KMP();
    return 0;
}