Cod sursa(job #3030643)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 17 martie 2023 19:40:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s,b;
vector<int> v;
const int NMAX=4000007;
int i,j,patsiz,maxpros;
int z[NMAX];
int main()
{
    in>>s>>b;
    patsiz=s.size();
    s.push_back('*');
    s.append(b);
    maxpros=0;
    for(i=1;i<s.size();i++)
    {
        //j=min(z[i],maxpros-i+1);
        j=0;
        while(s[j]==s[j+i]&&j+i<s.size())
        {
            z[i+j]=z[j];
            j++;
        }
        maxpros=max(maxpros,j+i);
        z[i]=j;
        if(z[i]==patsiz)
        {
            v.push_back(i);
        }
        if(v.size()==1000)
        {
            break;
        }
    }
    out<<v.size()<<"\n";
    for(auto w:v)
    {
        out<<w-patsiz-1<<" ";
    }
}