Cod sursa(job #1979769)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 11 mai 2017 12:59:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
int T[4000005];
char C[4000005];
int id=0;
int nr;
int N;
int V[1005];
int main()
{
    fgets(C+1,2000005,f);N=strlen(C+1);N=N-(C[N]=='\n');C[N+1]='$';T[1]=N;
    fgets(C+2+N,2000005,f);N=strlen(C+1);N=N-(C[N]=='\n');
    for(int i=2;i<=N;i++)
    {
        if(id+T[id]-1>=i)T[i]=min(T[i-id+1],id+T[id]-i);
        while(C[i+T[i]]==C[1+T[i]])
            T[i]++;
        if(T[i]==T[1])
        {
            nr++;
            if(nr<=1000)
                V[nr]=i-T[1]-2;
        }
        if(id+T[id]<i+T[i])
            id=i;
    }
    fprintf(g,"%d\n",nr);
    for(int i=1;i<=nr&&i<=1000;i++)fprintf(g,"%d ",V[i]);
    fclose(f);
    fclose(g);
    return 0;
}