Cod sursa(job #1741155)

Utilizator razvandRazvan Dumitru razvand Data 13 august 2016 02:00:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int Z[2*2000003];

void ZF(string s) {

    int left = 0;
    int right = 0;

    for(int k = 0; k < s.size(); k++) {

        if(k > right) {
            left = k;
            right = k;
            while(right < s.size() && s[right] == s[right-left])
                right++;
            Z[k] = right-left;
            right--;
        } else {

            int p = k+Z[k-left];

            if(p <= right)
                Z[k] = Z[p];
            else {
                left = k;
                while(right < s.size() && s[right] == s[right-left])
                    right++;
                Z[k] = right-left;
                right--;
            }

        }

    }

}

int main() {

    string s1,s2,rez;
    in >> s1 >> s2;
    rez = s1 + "$" + s2;

    ZF(rez);
    int K = 0;

    int am = 0;
    for(int i = 0; i < rez.size(); i++) {
        if(Z[i] == s1.size())
            am++;
    }

    out << am << '\n';

    for(int i = 0; i < rez.size(); i++) {

        if(Z[i] == s1.size()) {

            if(++K > 1000)
                break;
            out << i-s1.size()-1 << " ";

        }

    }

    return 0;
}