Cod sursa(job #2709308)

Utilizator VladMxPMihaila Vlad VladMxP Data 20 februarie 2021 10:14:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
vector<int> sol;

void z_algoritm(int n,int m)
{
    short int t[n+m+1];
    int z[n+m+1];
    for(int i=0;i<n;i++)
    {
        t[i]=a[i]-'0';
    }
    t[n]=-1;
    for(int i=0;i<m;i++)
    {
        t[n+i+1]=b[i]-'0';
    }
    m=n+m+1;
    int st=0,dr=0;
    z[0]=0;
    for(int k=1;k<m;k++)
    {
        if(k>dr)
        {
            st=dr=k;
            while(t[dr]==t[dr-st]&&dr<m)
                dr++;
            z[k]=dr-st;
            dr--;
        }
        else
        {
            int i=k-st;
            if(k+z[i]<=dr)z[k]=z[i];
            else
            {
                st=k;
                while(t[dr]==t[dr-st]&&dr<m)
                    dr++;
                z[k]=dr-st;
            }
        }
        if(z[k]==n)
        {
            sol.push_back(k-n-1);
        }
    }
}
int main()
{
    fin.getline(a,2000001);
    fin.getline(b,2000001);
    z_algoritm(strlen(a),strlen(b));
    fout<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)fout<<sol[i]<<" ";
}