Cod sursa(job #2722588)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 13 martie 2021 00:02:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <cstring>
#define dim 2000010
using namespace std;
char a[dim];
char b[dim];
int sol[1010];
int p[dim];
int i,j,n,m,u;

void prefix (char a[]) {
    j=0;
    for (i=2;a[i]!=0;i++) {
        while (j&&a[i]!=a[j+1]) {
            j=p[j];
        }
        if (a[i]==a[j+1]) {
            p[i]=++j;
        }
    }
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    prefix(a);
    j=0;
    for (i=1;i<=m;i++) {
        while (j&&a[j+1]!=b[i]) {
            j=p[j];
        }
        if (a[j+1]==b[i]) {
            j++;
        }
        if (j==n) {
            u++;
            if (u<=1000) sol[u]=i-n;
        }
    }
    fout<<u<<"\n";
    for (i=1;i<=min(u,1000);i++) {
        fout<<sol[i]<<" ";
    }
   /* for(i=1;i<=n;i++) {
        fout<<p[i]<<" ";
    } */
    return 0;
}