Cod sursa(job #2723133)

Utilizator NashikAndrei Feodorov Nashik Data 13 martie 2021 16:25:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int z[4000005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string s1,s2;
    cin>>s1;
    cin>>s2;

    int n=s1.size();
    int m=s2.size();
    s1+='#';
    s1+=s2;
    int lung=n+m+1;
    int st=0,dr=0;
    for(int i=1;i<lung;i++){
        if(i<=dr){
            if(z[i-st]+i-1<dr)
                z[i]=z[i-st];
            else{
                st=i;
                while(s1[dr]==s1[dr-st] and dr<=lung){
                    dr++;
                }
                z[i]=dr-st;
                dr--;
            }
        }
        else{
            st=i;
            dr=i;
            while(s1[dr]==s1[dr-st] and dr<=lung){
                dr++;
            }
            z[i]=dr-st;
            dr--;
        }
    }
    int contor=0;
    for(int i=0;i<lung;i++){
        //cout<<z[i]<<" ";
        if(z[i]==n){
            contor++;
        }
    }
    cout<<contor<<"\n";
    contor=min(contor,1000);
    for(int i=n+1;i<lung;i++){
        if(contor==0)
            break;
        if(z[i]==n){
            cout<<i-n-1<<" ";
            contor--;
        }
    }
    return 0;
}