Cod sursa(job #2420135)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 10 mai 2019 18:47:00
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 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;

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++;
    }
    g<<ans<<'\n';
    if(ans<=1000)
    {
        for(int i=0;i<lgB;i++)
        if(Di[i]==lgA) g<<i-lgA<<" ";
    }
    else
    {
        int cnt=0;
        for(int i=0;i<lgB&&cnt<=1000;i++)
        if(Di[i]==lgA)
        {
            g<<i-lgA<<" ";
            cnt++;
        }
    }

    return 0;
}