Cod sursa(job #2835048)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 17 ianuarie 2022 23:26:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, z[2000005], zz, num;
string s1, s2;
vector <int> rez;
void p_preg()
{
    for(int i=1, l=0, r=0; i<n; i++)
    {
        if(i<=r)  z[i]=min(z[i-l], r-i+1);
        while(i+z[i]<n && s1[i+z[i]]==s1[z[i]])
             z[i]++;
        if(i+z[i]-1>r) l=i, r=i+z[i]-1;
    }
}
void ZZ()
{
    if(n>m)  return;
    for(int i=0, l=0, r=0; i<m; i++)
    {
        if(i<=r)  zz=min(z[i-l], r-i+1);
        while(i+zz<m  && zz<n && s2[i+zz]==s1[zz])
            zz++;
        if(zz==n)
        {
            num++;
            if(num<=1000) rez.push_back(i);
        }
        if(i+zz-1>r)  l=i, r=i+zz-1;
        zz=0;
    }
}
int main()
{
    fin >> s1 >> s2;
    n=s1.length(), m=s2.length();
    p_preg();
    ZZ();
    fout << num << "\n";
    for(int i=0; i<rez.size(); i++)  fout << rez[i] << " ";
    return 0;
}