Cod sursa(job #2561947)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 29 februarie 2020 11:16:17
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#define Dim 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int dp[Dim],dpp[Dim],N,M,K,ans,S[1001];
char A[Dim],B[Dim];

int main()
{
    f>>A>>B;
    N=strlen(A); M=strlen(B);

    for(int i=N-1;i>=0;i--) A[i+1]=A[i];
    for(int i=M-1;i>=1;i--) B[i+1]=B[i];

    dp[1]=0;
    for(int i=2;i<=N;i++)
    {
        K=dp[i-1];
        while( K > 0 && A[i] != A[ K + 1 ] ) K=dp[K];

        if( A[i] == A[ K + 1 ] ) dp[i]=K+1;
    }

    dpp[0]=0;
    for(int i=1;i<=M;i++)
    {
        K=dpp[i-1];
        while( K > 0 && B[i] != A[ K + 1 ] ) K=dp[K];
        if( B[i] == A[ K + 1 ] ) dpp[i]=K+1;

        if( dpp[i] == N )
        {
            ans++;
            if(ans<=100) S[ans]=i-N;
        }
    }
    g<<ans<<'\n';
    for(int i=1;i<=ans;i++) g<<S[i]<<' ';

    return 0;
}