Cod sursa(job #2439000)

Utilizator Ioana_GaborGabor Ioana Ioana_Gabor Data 14 iulie 2019 15:40:55
Problema Potrivirea sirurilor Scor 98
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb

#include <iostream>
#include <fstream>
#include <string>
#define NMAX 2000000
#define REZMAX 1000

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string a,b;
int la,lb,pi[NMAX+5],k,lrez,rez[REZMAX+5];

void init(){
    k=0;
    pi[1]=0;
    for(int i=2;i<=la;i++){
        while(k!=0&&a[k+1]!=a[i]){
            k=pi[k];
        }
        if(a[k+1]==a[i]){
            k++;
        }
        pi[i]=k;
    }
}

int main(){
    f>>a>>b;
    la=a.size();
    lb=b.size();
    for(int i=la;i>=0;i--){
        a[i+1]=a[i];
    }
    for(int i=lb;i>=0;i--){
        b[i+1]=b[i];
    }
    init();
    k=0;
    for(int i=1;i<=lb;i++){
        while(k!=0&&a[k+1]!=b[i]){
            k=pi[k];
        }
        if(a[k+1]==b[i]){
            k++;
        }
        if(k==la){
            lrez++;
            if(lrez<=REZMAX){
                rez[lrez]=i-la;
            }
            k=pi[k];
        }
    }
    g<<lrez<<'\n';
    lrez=min(lrez,REZMAX);
    for(int i=1;i<=lrez;i++){
        g<<rez[i]<<' ';
    }
    f.close();
    g.close();
}