Cod sursa(job #2488852)

Utilizator NashikAndrei Feodorov Nashik Data 7 noiembrie 2019 18:20:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
//#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int z[4000005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string p,s,total="";
    int l=0,r=0,len,l1;
    cin>>p;
    cin>>s;
    total+=p;
    total+='$';
    total+=s;
    len=total.size();
    l1=p.size();
    for(int i=1;i<len;i++){
        if(i>r){
            l=i;
            r=i;
            while(r<len and total[r]==total[r-l]){
                r++;
            }
            z[i]=r-l;
            r--;
        }
        else{
            if(z[i-l]<r-i){
                z[i]=z[i-l];
            }
            else{
                l=i;
                while(r<len and total[r]==total[r-l]){
                    r++;
                }
                z[i]=r-l;
                r--;
            }
        }
    }
    //cout<<"0 ";
    int cnt=0;
    for(int i=1;i<len;i++){
        if(z[i]==l1){
            cnt++;
        }
    }
    cout<<cnt<<"\n";
    if(cnt>1000)
        cnt=1000;
    for(int i=1;i<len;i++){
        if(cnt==0)
        break;
        if(z[i]==l1 and cnt!=0){
            cnt--;
            cout<<i-l1-1<<" ";
        }
    }
    return 0;
}