Cod sursa(job #2834998)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 17 ianuarie 2022 22:58:05
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 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[2000005], num;
string s1, s2;
vector <int> rez;
void ZZ()
{
    if(n>m)  return;
    for(int i=1, l=0, r=0; i<m; i++)
    {
        if(i<=r)  zz[i]=min(z[i-l], r-i+1);
        while((i+zz[i]<m && zz[i]<n) && s2[i+zz[i]]==s1[zz[i]])
            zz[i]++;
        if(zz[i]==n)
        {
            num++;
            if(num<=1000) rez.push_back(i);
        }
        if(i+zz[i]-1>r)  r=i+zz[i]-1;
    }
}
int main()
{
    fin >> s1 >> s2;
    n=s1.length(), m=s2.length();
    ZZ();
    fout << num << "\n";
    for(int i=0; i<rez.size(); i++)  fout << rez[i] << " ";
    return 0;
}