Cod sursa(job #2288889)

Utilizator aditzu7Adrian Capraru aditzu7 Data 24 noiembrie 2018 08:52:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <string.h>
#include <fstream>
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");

using namespace std;
char v[2000005],a[2000005];
int sol[100004],nr,i,k,p[2000005];
int main()
{
    fscanf(f,"%s\n%s",v+1,a+1);
    int n=strlen(v+1);
    int m=strlen(a+1);
k=0;
for(int i=2;i<=n;i++)
   {

    while(k&&v[k+1]!=v[i])
    k=p[k];

if(v[k+1]==v[i]) k++;
p[i]=k;
   }
   k=0;
   for(i=1;i<=m;i++){
   while(k&&v[k+1]!=a[i]) k=p[k];
   if(v[k+1]==a[i]) k++;
   if(k==n){
    nr++;
    if(nr<=1000) sol[nr]=i-n;
   }


   }
      fprintf(g,"%d\n",nr);
   for(i=1;i<=min(nr,1000);i++) fprintf(g,"%d ",sol[i]);

    return 0;
}