Cod sursa(job #2457813)

Utilizator kywyPApescu tiGEriu kywy Data 18 septembrie 2019 19:29:00
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<bits/stdc++.h>
#define NMAX 2000007
using namespace std;

FILE* in=fopen("strmatch.in", "r");
FILE* out=fopen("strmatch.out", "w");
char A[NMAX];
int v[NMAX], ct, pos[NMAX];

int main()
{
    char x;

    for(int i=1; ; ++i)
    {
        x=fgetc(in);

        if(x=='\n') break;
        else A[i]=x;

        int index=i-1;
        while(index)
        {
            index=v[index];
            if(A[index+1]==x&&index+1<i)
            {
                v[i]=index+1;
                break;
            }
        }
    }
    //for(int i=1; A[i]>0; ++i) fprintf(out, "%d ", v[i]);
    int index=0;
    for(int i=1; ; ++i)
    {
        x=fgetc(in);
        if(x=='\n') break;
        ++index;
        if(x!=A[index])
        {
            index=v[index];
            if(A[index+1]!=x) index=0;
        }
        else
        {
            if(!A[index+1])
            {
                ++ct;
                pos[ct]=i-index;
                index=v[index];
            }
        }
    }
    fprintf(out, "%d\n", ct);
    for(int i=1; i<=ct; ++i) fprintf(out, "%d ", pos[i]);
}