Cod sursa(job #3004988)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 16 martie 2023 18:37:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <cstring>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,j,cnt,p[DIM],sol[1001];
char a[DIM],b[DIM];
int main() {
    fin>>(a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    p[1]=0;
    j=0;
    for (i=2;i<=n;i++) {
        while (j!=0 && a[i]!=a[j+1])
            j=p[j];
        if (a[i]==a[j+1])
            j++;
        p[i]=j;
    }
    j=0;
    for (i=1;i<=m;i++) {
        while (j!=0 && b[i]!=a[j+1])
            j=p[j];
        if (b[i]==a[j+1])
            j++;
        if (j==n) {
            cnt++;
            if (cnt<=1000)
                sol[cnt]=i-n;
            j=p[j];
        }
    }
    fout<<cnt<<"\n";
    for (i=1;i<=min(cnt,1000);i++)
        fout<<sol[i]<<" ";
    return 0;
}