Cod sursa(job #857165)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 17 ianuarie 2013 15:04:32
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <cstring>

#define MAX 2000005
#define pb push_back

using namespace std;

char A[MAX], B[MAX];
int ap, aLgt, bLgt, Z[MAX];
vector<int> V;

int main()
{
    ifstream in("strmatch.in"); in.getline(A, MAX); in.getline(B, MAX); in.close();
    aLgt = strlen(A), bLgt = strlen(B);
    for(int i = 1, R = 1; i < aLgt; i++)
    {
        Z[i] = min(max(0, R - i), Z[R - i]);
        for(int j = i + Z[i]; A[Z[i]] == A[j] && j < aLgt; Z[i]++, j++);
        if(i + Z[i] > R) R = i + Z[i];
    }
    for(int i = 0, R = 0, poz = 0; i < bLgt; i++)
    {
        poz = min(max(0, R - i), Z[R - i]);
        for(int j = i + poz; B[j] == A[poz] && poz < aLgt; poz++, j++);
        if(poz == aLgt)
        {
            ap++;
            if(V.size() <= 1000) V.pb(i);
        }
        R = max(R, i + poz);
    }
    ofstream out("strmatch.out"); out<<ap<<"\n";
    for(size_t i = 0; i < V.size(); i++) out<<V[i]<<" ";
    out.close();
    return 0;
}