Mai intai trebuie sa te autentifici.

Cod sursa(job #2319244)

Utilizator TheSeekerRobert Cristian Dobra TheSeeker Data 13 ianuarie 2019 20:54:59
Problema Potrivirea sirurilor Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <string>
#define MAX 2000004
using namespace std;

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

int na,nb,i,j,x[MAX],y[MAX];
string a,b;

void chestie(){
    for (i=2;i<=na;i++){
        while (j && a[j+1]!=a[i])
            j=x[j];
        if (a[j+1]==a[i])
            j++;
        x[i]=j;
    }
}

int main(){
    fin>>a>>b;
    na=a.length();
    nb=b.length();
    for (i=na-1;i>=0;i--)
        a[i+1]=a[i];
    for (i=nb-1;i>=0;i--)
        b[i+1]=b[i];
    chestie();
    for (i=1;i<=nb;i++){
        while (j && a[j+1]!=b[i])
            j=x[j];
        if (a[j+1]==b[i])
            j++;
        if (j==na){
            j=x[j];
            y[0]++;
            y[y[0]]=i-na+1;
        }
    }
    fout<<y[0]<<'\n';
    y[0]=min(y[0],1000);
    for (i=1;i<=y[0];i++)
        fout<<y[i]-1<<" ";
    fin.close();
    fout.close();
    return 0;
}