Cod sursa(job #1508325)

Utilizator MKLOLDragos Ristache MKLOL Data 22 octombrie 2015 14:59:08
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define Nmax 2000002

char l[Nmax],v[Nmax];
int S1,S2,next[Nmax],rez[1234],r,ras;

void make() {
    int k=0;
    next[1]=0;
    for(int i=2;i<=S1;++i) {
        while(k >= 1 && v[k+1] != v[i]) k = next[k];
            if(v[k+1] == v[i]) ++k;
            next[i] = k;
    }
}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",v+1,l+1);
//printf("%s\n",v+1);
S1=strlen(v+1);
S2=strlen(l+1);

    make();
    int k=0;
    for(int i=1;i<=S2;++i) {
        while(k >= 1 && v[k+1] != l[i])
            k = next[k];
        if(v[k+1] == l[i]) ++k;
        if(k==S1) { // match at i-S1
            k = next[k];
            ++ras;
            if(r < 1000) rez[++r]=i-S1;
        }
    }
    printf("%d\n",ras);
    for(int i=1;i<=r;++i)
        printf("%d ",rez[i]);
}