Cod sursa(job #2562884)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 29 februarie 2020 19:25:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>
#include <iostream>
#define dim 2000004
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int la,lb,t[dim],i,lun,nrap;
char a[dim],b[dim];
vector<int> sol;
int main()
{
    fin>>(a+1)>>(b+1);
    la=strlen(a+1);
    lb=strlen(b+1);
    t[1]=0;
    for(i=2;i<=la;i++){
        while(lun!=0&&a[lun+1]!=a[i])
            lun=t[lun];
        if(a[lun+1]==a[i])
            lun++;
        t[i]=lun;
    }
    lun=0;
    for(i=1;i<=lb;i++){
        while(lun!=0&&a[lun+1]!=b[i])
            lun=t[lun];
        if(a[lun+1]==b[i])
            lun++;
        if(lun==la){
            nrap++;
            if(nrap<=1000){
                sol.push_back(i-la);
            }
            lun=t[lun];
        }
    }
    fout<<nrap<<"\n";
    for(auto it:sol)
        fout<<it<<" ";
}