Cod sursa(job #2717821)

Utilizator Serban04Serban Vizireanu Serban04 Data 7 martie 2021 23:14:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int N=2000002;
const int P=1000;

char a[N],b[N],c[N];
int pi[N];

int main()
{
    cin>>(1+a)>>(1+b);
    int lung=0,m=strlen(1+a),n=strlen(1+b);
    pi[1]=0;
    for (int i=2;i<=m;i++){
        while (lung>0 && a[i]!=a[lung+1]){
            lung=pi[lung];
        }
        if (a[i]==a[lung+1]){
            lung++;
        }
        pi[i]=lung;
    }
    lung=0;
    int nr=0;
    for (int i=1;i<=n;i++){
        while (lung>0 && b[i]!=a[lung+1]){
            lung=pi[lung];
        }
        if (b[i]==a[lung+1]){
            lung++;
        }
        if (lung==m){
            c[i-1]=1;
            nr++;
        }
    }
    cout<<nr<<"\n";
    nr=P;
    for (int i=0;i<n && nr>0;i++){
        if (c[i]){
            cout<<i-m+1<<" ";
            nr--;
        }
    }
    return 0;
}