Cod sursa(job #2443543)

Utilizator evelina.nitoiuNitoiu Evelina evelina.nitoiu Data 28 iulie 2019 15:00:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX=4000005;
vector <int> v;

int phi[NMAX];

int main()
{
    string a,b,s;
    in>>a>>b;
    s='#'+a+'*'+b;
    phi[0]=-1;
    for(int i=1;i<=s.size();i++){
        int x=i-1;
        while(x>0){
            if(s[i]==s[phi[x]+1])
                break;
            x=phi[x];
        }
        phi[i]=phi[x]+1;
    }
    int nr=0;
    for(int i=1;i<=s.size();i++)
        if(phi[i]==a.size())
        {
            nr++;
            v.push_back(i-a.size()-1-a.size());
        }
    out<<nr<<'\n';
    nr=min(nr,1000);
    for(int i=0;i<nr;i++)
        out<<v[i]<<" ";
    return 0;
}