Cod sursa(job #2421919)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 16 mai 2019 18:02:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#define Dim 2000009
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[Dim],B[Dim];
int lgA,lgB,Pi[Dim],Di[Dim],Poz[1005],ans,K;

int main()
{
    f.get(A,Dim); f.get();
    f.get(B,Dim);
    lgA=strlen(A); lgB=strlen(B);

    for(int i=lgA;i>=1;i--) A[i]=A[i-1];
    for(int i=lgB;i>=1;i--) B[i]=B[i-1];

    Pi[1]=0; K=Pi[1];
    for(int i=2;i<=lgA;i++)
    {
         while(K>0&&A[K+1]!=A[i]) K=Pi[K];
         if(A[i]==A[K+1]) K++;
         Pi[i]=K;
    }

    K=0;
    for(int i=1;i<=lgB;i++)
    {
        while(K>0&&B[i]!=A[K+1]) K=Pi[K];
        if(B[i]==A[K+1]) K++;
        Di[i]=K;

        if(Di[i]==lgA)
        {
            ans++;
            if(ans<=1000) Poz[ans]=i-lgA;
        }
    }

    g<<ans<<'\n';
    for(int i=1;i<=min(ans,1000);i++) g<<Poz[i]<<" ";

    return 0;
}