Cod sursa(job #2572746)

Utilizator NashikAndrei Feodorov Nashik Data 5 martie 2020 14:06:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
//#include <iostream>
#include <fstream>
using namespace std;
///algoritmul lui z
int z[4000005];
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size(),m=s2.size();
    s1+='#';
    s1+=s2;

    int st=0,dr=0;
    for(int i=1;i<n+m+1;i++){
        if(i>dr){
            dr=i;
            st=i;
            int ind=0;
            while(s1[dr]==s1[ind] and dr<n+m+1){
                dr++;
                ind++;
            }
            dr--;
            z[i]=ind;
        }
        else{
            if(z[i-st]+i-1<dr){
                z[i]=z[i-st];
            }
            else{
                st=i;
                dr=i;
                int ind=0;
                while(s1[dr]==s1[ind] and dr<n+m+1){
                    dr++;
                    ind++;
                }
                dr--;
                z[i]=ind;
            }
        }
    }
    //cout<<s1<<"\n";
    int contor=0;
    for(int i=0;i<n+m+1;i++){
        if(z[i]==n){
            contor++;
        }
    }
    cout<<contor<<"\n";
    contor=0;
    for(int i=0;i<n+m+1;i++){
        if(z[i]==n){
            contor++;
            if(contor<=1000)
            cout<<i-n-1<<" ";
        }
    }
    return 0;
}