Cod sursa(job #2574446)

Utilizator anamariatoaderAna Toader anamariatoader Data 5 martie 2020 22:23:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>

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

int v[2000005],l,n,nr,i,k,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,j=1;
    while(i<=n){
        if(a[j]==s[i]){
           if(j==l){
             nr++;
             if(nr<=1000)
               sol[nr]=i-l;
           }
           i++;
           j++;
        }
        else{
           if(j>1)
            j=v[j-1];
           else
             i++;
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<sol[i]<<' ';
    return 0;
}