Cod sursa(job #2441763)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 20 iulie 2019 22:39:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>

using namespace std;

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

string s;
const int N=(int)4e6+7;
int z[N];

void build_z()
{
        int l=-1,r=-1;
        int n=(int)s.size();
        for(int i=0;i<n;i++)
        {
                if(i<=r)
                        z[i]=min(z[i-l],r+1-i);
                while(i+z[i]<n && s[i+z[i]]==s[z[i]])
                        z[i]++;
                if(i+z[i]-1>r)
                        l=i,r=i+z[i]-1;
        }
}

int sol[1007],cnt;

int main()
{
        fin>>s;
        string t;
        fin>>t;
        s+=".";
        int L=s.size();
        s+=t;
        int R=s.size()-1;
        build_z();
        for(int j=L;j<=R;j++)
                if(z[j]==L-1)
                {
                        cnt++;
                        if(cnt<=1000)
                                sol[cnt]=j-L;
                }
        fout<<cnt<<"\n";
        /// i<=cnt, i<=1000
        for(int j=1;j<=min(cnt,1000);j++)
                fout<<sol[j]<<" ";
        fout<<"\n";
        return 0;
}