Cod sursa(job #2420139)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 10 mai 2019 18:56:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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],K;
int ans,Which[1005];

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];

    K=0;
    Pi[1]=0;
    for(int i=2;i<=lgA;i++)
    {
        while(K>0&&A[i]!=A[K+1]) 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) Which[ans]=i-lgA;
        }
    }
    g<<ans<<'\n';
    for(int i=1;i<=min(ans,1000);i++) g<<Which[i]<<" ";

    return 0;
}