Cod sursa(job #1469507)

Utilizator robertstrecheStreche Robert robertstreche Data 8 august 2015 15:32:59
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

#define LMAX 1000
#define NMAX 400001

using namespace std;

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

int st,dr,pas;
int z[NMAX];

string A,B,S;
vector <int>sol;

int main()
{
    f>>A>>B;
    S=A+'$'+B;
    int n=S.size()-1;

    for (int i=1;i<=n;i++){
    if (dr<i){
        st=i;
        for (dr=i;dr<=n && S[dr]==S[dr-st];dr++);

        dr--;
        z[i]=dr-st+1;
    }
    else {
        int poz=i-st;
        if (z[poz]+i<=dr)
            z[i]=z[poz];
        else {
            for (st=i;dr<n && S[dr]==S[dr-st];dr++);
            dr--;
            z[i]=dr-st+1;
        }
    }
    if (z[i]==A.size())sol.push_back(i-A.size()-1);
    }
    g<<sol.size()<<'\n';
    for (auto it:sol)
    {
        if (++pas>LMAX)break;
        g<<it<<" ";
    }
}