Cod sursa(job #1798356)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 5 noiembrie 2016 10:36:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
#include<string.h>
using namespace std;

FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");

char a[2000005],b[2000005];
int q,i,dim,k,v[1005],um[2000005];

int main() {

    fscanf(f,"%s%s",a,b);

    um[1]=0; k=0;
    for(i=2;i<=strlen(a);i++) {
        while(k>0&&a[k]!=a[i-1]) k=um[k];
        if(a[k]==a[i-1]) k++;
        um[i]=k;
    }
    q=0;
    for(i=0;i<strlen(b);i++) {
        while(q>0&&a[q]!=b[i]) q=um[q];
        if(a[q]==b[i]) q++;
        if(q==strlen(a)) {
            ++dim;
            if(dim<=1000) v[dim]=i-strlen(a)+1;
        }
    }
    fprintf(g,"%d\n",dim);
    if(dim>1000) dim=1000;
    for(i=1;i<=dim;i++) fprintf(g,"%d ",v[i]);

    fclose(f); fclose(g);

    return 0;
}