Cod sursa(job #2739412)

Utilizator stefantagaTaga Stefan stefantaga Data 8 aprilie 2021 10:25:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,s1,s2;
int poz[2000005],z[4000005],k,val,lim,i,q,st,dr,cop;
int main()
{
    f>>s;
    f>>s1;
    s2=s+'#'+s1;
    st=0;
    dr=0;
    for (i=1;i<s2.size();i++)
    {
        if (i<=dr)
        {
            z[i]=min(dr-i+1,z[i-st]);
        }
        while (i+z[i]<s2.size()&&s2[i+z[i]]==s2[z[i]])
        {
            z[i]++;
        }
        if (i+z[i]-1>dr)
        {
            st=i;
            dr=i+z[i]-1;
        }
        if (z[i]==s.size())
        {
            poz[++q]=i-s.size()-1;
        }
    }
    g<<q<<'\n';
    lim=min(q,1000);
    for (i=1;i<=lim;i++)
    {
        g<<poz[i]<<" ";
    }
    return 0;
}