Cod sursa(job #2857606)

Utilizator dolorentiuDaniel Gadalean dolorentiu Data 25 februarie 2022 22:14:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
#include <fstream>
#define MAX 2000005
#define pb push_back
using namespace std;

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

char a[MAX],b[MAX];
int M,N,p[MAX],pos[1001];


void cit(){
    f.getline(a,MAX);
    f.getline(b,MAX);
}

void prefix(){
    int k=0;
    p[1]=0;
    for(int i=2;i<=M;i++){
        while(k && a[k+1]!=a[i])
            k=p[k];
        if(a[k+1]==a[i])
            k++;
        p[i]=k;
    }
}
//void afis(){
//    for(int i=n;i>=1;i--)
//        g<<sol[i]<<' ';
//}

int main()
{
    int k=0,n=0;
    cit();
    M=strlen(a);
    N=strlen(b);
    for(int i=M;i;i--)a[i]=a[i-1]; a[0]=' ';
    for(int i=N;i;i--)b[i]=b[i-1]; b[0]=' ';

    prefix();

    for(int i=1;i<=N;i++){
        while(k && a[k+1]!=b[i])
            k=p[k];
        if(a[k+1]==b[i])
            k++;
        if(k==M){
            k=p[M];
            n++;
            if(n<=1000)
                pos[n]=i-M;
        }
    }
    g<<n<<'\n';
    for(int i=1;i<=min(n,1000);i++)
        g<<pos[i]<<" ";
    return 0;
}