Cod sursa(job #2480822)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 26 octombrie 2019 10:32:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstring>
#include <cstdio>
#include <algorithm>
#define NMAX 2000005
using namespace std;

char a[NMAX];
char b[NMAX];
int p[NMAX];
int rez[1005];
int m, n, nr=0;
void formPrefix(){
    int i=0;
    for(int j=2; j<=n; j++){
        while(i>0 && a[i+1]!=a[j])
            i=p[i];
        if(a[i+1]==a[j])
            ++i;
        p[j]=i;
    }
}

void strmatch(){

    int k=0;
    for(int j=1; j<=m; j++){
        while(k>0 && a[k+1]!=b[j])
            k=p[k];
        if(a[k+1]==b[j])
            ++k;
        if(k==n){
            nr++;
            if(nr<=1000)
                rez[nr]=j-k;
        }
    }
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n", (a+1));
    scanf("%s", (b+1));
    n=strlen(a+1);
    m=strlen(b+1);
    formPrefix();
    //for(int i=0; i<=n; i++)
    //    printf("%d", p[i]);

    ///printf("\n");
    strmatch();
    printf("%d\n",nr);
    int panaunde=min(nr,1000);
    for(int i=1; i<=panaunde;i++)
        printf("%d " ,rez[i]);
    return 0;
}