Cod sursa(job #998378)

Utilizator harababurelPuscas Sergiu harababurel Data 16 septembrie 2013 20:52:15
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 4000005
using namespace std;

string a, b, s;
int Z[nmax];
int L = 0, R = 1, k, kprim, i, j, cnt;


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

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

    for(k = 1; k < s.size(); k++) {
        if(s[k] != s[0]) { Z[k] = 0; continue; }
        if(k > R) {
            i = 0;
            j = k;
            while(j < s.size() && s[i] == s[j]) i++, j++;

            L = k;
            R = j-1;
            Z[k] = R - L + 1;
        }

        else {
            kprim = k - L;

            if(k==10)
                cout<<s[k]<<": k = "<<k<<" si k' = "<<kprim<<"\n";

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

                L = k;
                R = j;
                Z[k] = Z[kprim] + R - L + 1;
            }
        }
    }

    Z[0] = 0;
    //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=0; i<s.size(); i++)
        if(Z[i] >= a.size() && i >= a.size()) cnt++;

    g<<cnt<<"\n";
    cnt = min(cnt, 1000);
    for(int i=0; i<s.size(); i++)
        if(cnt && Z[i] >= a.size() && i >= a.size())
            g<<i-a.size()<<" ", cnt--;

    return 0;
}