Cod sursa(job #2709329)

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

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

void z_algoritm(int n,int m)
{
    for(int i=0;i<n;i++)
    {
        t[i]=a[i];
    }
    t[n]=-1;
    for(int i=0;i<m;i++)
    {
        t[n+i+1]=b[i];
    }
    m=n+m+1;
    int st=0,dr=0,i;
    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
        {
            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;
                dr--;
            }
        }
        if(z[k]==n)
        {
            sol.push_back(k-n-1);
        }
    }
}
int main()
{
    fin.getline(a,2000005);
    fin.getline(b,2000005);
    z_algoritm(strlen(a),strlen(b));
    fout<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)fout<<sol[i]<<" ";
}