Cod sursa(job #2739036)

Utilizator NashikAndrei Feodorov Nashik Data 6 aprilie 2021 18:30:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int z[4000005];
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int x=s1.size();
    int y=s2.size();
    s1+='$';
    s1+=s2;
    int n=s1.size();
    int st=0,dr=0;
    for(int i=1;i<n;i++){
        if(i<=dr){
            if(z[i-st]+i<=dr){
                z[i]=z[i-st];
            }
            else{
                st=i;
                while(s1[dr]==s1[dr-st] and dr<=n){
                    dr++;
                }
                z[i]=dr-st;
                dr--;
            }
        }
        else{
            st=i;
            dr=i;
            while(s1[dr]==s1[dr-st] and dr<=n){
                dr++;
            }
            z[i]=dr-st;
            dr--;
        }
    }
    int contor=1000,cnt=0;
    for(int i=x;i<n;i++){
        if(z[i]==x and contor!=0){
            cnt++;
        }
    }
    cout<<cnt<<"\n";
    for(int i=x;i<n;i++){
        if(z[i]==x and contor!=0){
            contor--;
            cout<<i-x-1<<" ";
        }
    }
    return 0;
}