Cod sursa(job #3149558)

Utilizator DariusM17Murgoci Darius DariusM17 Data 9 septembrie 2023 19:38:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
#define ll long long
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
string a,c ;
int z[4000005],n,m,st,dr ;
vector <int> pos ;
int main()
{
    fin>>a ;
    m=a.size(),c=a+"#";
    fin>>a ;
    c+=a ;
    n=c.size() ;
    for(int i=1; i<n; ++i)
    {
        if(i>dr)
        {
            st=dr=i ;
            while(dr<n && c[dr]==c[dr-st]) dr++ ;
            dr--,z[i]=dr-st+1 ;
        }
        else
        {
            if(i+z[i-st]<=dr) z[i]=z[i-st] ;
            else
            {
                st=i ;
                while(dr<n && c[dr]==c[dr-st]) dr++ ;
                z[i]=dr-st ;
            }
        }
        if(z[i]==m && i>m) pos.push_back(i-2*m+2) ;
    }
    fout<<pos.size()<<'\n' ;
    for(int i=0; i<min((int)pos.size(),1000); ++i) fout<<pos[i]<<" ";
    return 0;
}