Cod sursa(job #998652)

Utilizator harababurelPuscas Sergiu harababurel Data 17 septembrie 2013 19:56:56
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 4000005
using namespace std;

vector <int> v;

string a, b, s;
int Z[nmax];
int L = 0, R = 0, B, n, k, kprim, i, j, sol = 0;


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

    getline(f, a);
    getline(f, b);
    s = a + b;
    Z[0] = s.size();
    n = s.size();

    for(int k=1; k<n; k++) {
        if(s[k] != s[0]) continue;      //n-am treaba pe-aici

        if(k >= R) {
            i = 0;
            j = k;
            while(j < n && s[i] == s[j]) Z[k]++, i++, j++;

            L = k;
            R = k + Z[k] - 1;
        }
        else {
            kprim = k - L;
            B = R - k + 1;

            if(Z[kprim] <= B) Z[k] = Z[kprim];
            else {
                Z[k] = B;
                i = R - L + 1;
                j = R + 1;
                while(j < n && s[i] == s[j]) Z[k]++, i++, j++;
                L = k;
                R = k + Z[k] - 1;
            }
        }

        //cout<<"Dupa k = "<<k<<" (litera <"<<s[k]<<">), L = "<<L<<" si R = "<<R<<"\n";
    }


    //cout<<"\n ";
    //for(int i=0; i<s.size(); i++) cout<<s[i]<<" "; cout<<"\n";
    //for(int i=0; i<s.size(); i++) cout<<Z[i]<<" "; cout<<"\n";


    for(int i=a.size(); i<n; i++)
        if(Z[i] >= a.size()) sol++, v.push_back(i-a.size());

    g<<sol<<"\n";
    for(int i=0; i<min(int(v.size()), 999); i++) g<<v[i]<<" ";








    return 0;
}