Cod sursa(job #1749066)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 27 august 2016 20:04:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 4e6 + 5;

string txt, pat, cat;
int z[NMAX];

int main(void) {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int n, m, k, l, r, ant;

    ant = 0;
    l   = 0;
    r   = -1;

    f>>pat>>txt;
    cat = pat + "#" + txt;

    for (int i=1; i<cat.size(); ++i) {
        if (i>r) {
            for(l=r=i; cat[r-l]==cat[r] && r<cat.size(); ++r);
            z[i] = r - l;
            --r;
        }
        else {
            k = i - l;
            if (z[k] < r-i+1) {
                z[i] = z[k];
            }
            else {
                l = i;
                for(; r<cat.size() && cat[r-l]==cat[r]; ++r);
                z[i] = r - l;
                --r;
            }
        }
    }

    for(int i=pat.size(); i<cat.size(); ++i)
        if(z[i]>=pat.size())
            ++ant;

    g<<ant<<'\n';
    ant = min(ant, 1000);

    for(int i=pat.size(); ant && i<cat.size(); ++i)
        if(z[i]>=pat.size())
            g<<i-pat.size()-1<<' ',
            --ant;
    g<<'\n';

    f.close();
    g.close();
    return 0;
}