Cod sursa(job #2739091)

Utilizator sandifx68Fazakas Alexandru sandifx68 Data 6 aprilie 2021 20:03:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

ifstream f("strmatch.in");
ofstream g("strmatch.out");


char a[2000005],b[2000005];
int l[2000005],lv[1001];
int n,m,i=1,j,nr,cati;

int main()
{
    f>>a;m=strlen(a);
    while(i<m)
        if(a[i]==a[j])
        {
            l[i]=j+1;
            i++,j++;
        }
        else
            if(j==0)l[i++]=0;
                else j=l[j-1];
    f>>b;n=strlen(b);
    i=0;j=0;
    while(i<n){
        if(b[i]==a[j]){
            i++;j++;
            if(j==m){
                cati++;
                if(cati<=1000)
                    lv[cati]=i-j;
                j=l[j-1];
            }
        }
        else {
            if(j==0)i++;
            else j=l[j-1];
        }
    }
    g<<cati<<"\n";
    for(i=1;i<=min(cati,1000);i++)
        g<<lv[i]<<" ";
}