Cod sursa(job #2574322)

Utilizator anamariatoaderAna Toader anamariatoader Data 5 martie 2020 21:33:42
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int v[200005],l,n,nr,i,j,sol[1005];
char a[2000005],s[2000005];

int main(){
    fin>>(a+1)>>(s+1);
    l=strlen(a+1);
    n=strlen(s+1);
    j=1; i=2;
    v[0]=v[1]=1;
    while(i<=l){
        if(a[i]==a[j]){
            v[i]=j+1;
            i++;
            j++;
        }
        else{
            v[i]=1;
            j=v[i-1];
            i++;
        }
    }
    i=1;
    for(j=1;j<=n;j++){
        if(a[i]==s[j]){
            i++;
            if(i==l+1){
                i=v[i-1];
                nr++;
                if(nr<=1000)
                    sol[nr]=j-l;
            }
        }
        else{
            i=v[i-1];
            if(a[i]==s[j]){
                i++;
            }
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<sol[i]<<' ';
    return 0;
}