Cod sursa(job #1963991)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 12 aprilie 2017 23:06:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define in "strmatch.in"
#define out "strmatch.out"
#define NMAX (2000000 + 7)
#define pb push_back

using namespace std;
char A[NMAX], B[NMAX];
int phi[NMAX], szeA, szeB, ct;
vector <int> sol;

inline void prefix()
{
    phi[1] = 0;
    int k = 0;
    for(int i = 2; i<= szeA; ++i)
    {
        while(A[k+1] != A[i] && k) k = phi[k];
        if(A[k+1] == A[i]) ++k;
        phi[i] = k;
    }
}
inline void stringMatch()
{
    int k = 0;
    for(int i = 1; i<= szeB; ++i)
    {
        while(A[k+1] != B[i] && k) k = phi[k];
        if(A[k+1] == B[i]) ++k;
        if(k == szeA)
        {
            ++ct;
            if(ct <= 1000)
            {
                sol.pb(i-szeA);
            }
        }
    }
}
inline void afisare()
{
    printf("%d\n", ct);
    for(int i = 0; i< min(1000, ct); ++i) printf("%d ", sol[i]);
    printf("\n");
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%s\n%s\n", A+1, B+1);
    szeA = strlen(A+1);
    szeB = strlen(B+1);
    prefix();
    stringMatch();
    afisare();
    return 0;
}