Cod sursa(job #857175)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 17 ianuarie 2013 15:16:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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 + 1, MAX); in.getline(B + 1, MAX); in.close();
    aLgt = strlen(A + 1), bLgt = strlen(B + 1);
    for(int i = 2, R = 1, index = 0, sw = 0; i <= aLgt; i++, sw = 0)
    {
        Z[i] = min(max(0, R - i + 1), Z[i - index + 1]);
        for(int j = i + Z[i]; A[Z[i] + 1] == A[j] && j < aLgt; Z[i]++, j++, sw = 1);
        if(i + Z[i] - 1 > R) R = i + Z[i] - 1, index = i;
    }
    for(int i = 1, R = 0, poz = 0, index = 0, sw = 0; i <= bLgt; i++, sw = 0)
    {
        poz = min(max(0, R - i + 1), Z[i - index + 1]);
        for(int j = i + poz; B[j] == A[poz + 1] && poz < aLgt; poz++, j++, sw = 1);
        //if(sw) poz--;
        if(poz == aLgt)
        {
            ap++;
            if(V.size() <= 1000) V.pb(i);
        }
        if(i + poz - 1 > R) R = i + poz - 1, index = i;
    }
    ofstream out("strmatch.out"); out<<ap<<"\n";
    for(size_t i = 0; i < V.size(); i++) out<<V[i] - 1<<" ";
    out.close();
    return 0;
}