Cod sursa(job #2739068)

Utilizator sandifx68Fazakas Alexandru sandifx68 Data 6 aprilie 2021 19:19:12
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

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


char a[2000005],b[2000005],l[2000005];
int n,m,i=1,j,nr;
vector <int>lv;

int main()
{
    fscanf(f,"%s",a);n=strlen(a);
    while(i<n)
        if(a[i]==a[j])
        {
            l[i]=j+1;
            i++,j++;
        }
        else
            if(j==0)l[i++]=0;
                else j=l[j-1];
    fscanf(f,"%s",b);m=strlen(b);
    while(i<m){
        if(b[i]==a[j]){
            i++,j++;
            if(j==n){
                lv.push_back(i-j);
                j=l[j-1];
            }
        }
        else {
            if(j==0)i++;
            else j=l[j-1];
        }
    }
    fprintf(g,"%d\n",lv.size());
    if(lv.size()<1000) n=lv.size();
    else n=1000;
    for(i=0;i<n;i++)
        fprintf(g,"%d ",lv.at(i));
}